In this blog post, we learn how to write a C program to rotate an array left and right by a given number K? So here we will write a C program to rotate an array left and right by a given number K.
Suppose ‘arr’ is an integer array of size N and task to rotate the array to the left or right by k steps, where k is non-negative. Here, array rotation means shifting the array elements to the left or right of the array by specified positions.
Example,
Input: int arr[] = {1,2,3,4,5,6,7}, k = 3
Output: {5,6,7,1,2,3,4}
Explanation:
rotate 1 steps to the right-> {7,1,2,3,4,5,6}
rotate 2 steps to the right-> {6,7,1,2,3,4,5}
rotate 3 steps to the right-> {5,6,7,1,2,3,4}Let’s see some solution to rotate an array left and right by a given number K. But it would be great if you try to solve this problem yourself first.
Solution 1:
In this solution, first, we will create two functions to shift the array element one position to left and right. After creating these two functions we call them in other functions where they will be called in the loop according to the value of ‘k’.
In the one left shift function, we will create an intermediate temp variable to store the first element ( arr[0] ) array. Now we will move arr[1] to arr[0], arr[2] to arr[1] …and finally temp to arr[n-1]. This technique will rotate the array element 1 position.
In the right shift, we need to store the last element of the array in the temp variable and move the arr[n-2] to arr[n-1], arr[n-3] to arr[n-2] …and finally temp to arr[0].
If you want to learn more about the C language, you can check this course, Free Trial Available.
Let’s see the c program to left and right rotate array elements by kth position.
#include <stdio.h>
#include <stdint.h>
//Calculate array size
#define ARRAY_SIZE(arr) sizeof(arr)/sizeof(arr[0])
// Function to right-rotate an array by one position
void rightRotateByOne(int arr[], int arr_size)
{
int i;
//take last element of the array
int last = arr[arr_size - 1];
for (i = arr_size - 2; i >= 0; i--)
{
arr[i + 1] = arr[i];
}
// Now store the last element
// at 0th index of the array
arr[0] = last;
}
// Function to left-rotate an array by one position
void leftRotatebyOne(int arr[], int arr_size)
{
//get first element of the array
int first = arr[0], i;
for (i = 0; i < arr_size - 1; i++)
{
arr[i] = arr[i + 1];
}
arr[i] = first;
}
//Function to left rotate an array by 'k' positions
void leftRotate(int arr[], int k, int arr_size)
{
int i;
for (i = 0; i < k; i++)
{
leftRotatebyOne(arr, arr_size);
}
}
// Function to right-rotate an array by 'k' positions
void rightRotate(int arr[], int k, int arr_size)
{
int i;
for (i = 0; i < k; i++)
{
rightRotateByOne(arr, arr_size);
}
}
//print the array elements
void printArray(int arr[], int arr_size)
{
int i;
for (i = 0; i < arr_size; i++)
{
printf("%d ", arr[i]);
}
printf("\n\n");
}
int main()
{
//array must be sorted
int arr[] = {8, 11, 13, 15, 1, 4, 6};
//get array size
int arr_size = ARRAY_SIZE(arr);
printf("Original Array = ");
printArray(arr, 7);
printf("Left shift array by 2 = ");
leftRotate(arr, 2, arr_size);
printArray(arr, 7);
printf("Right shift array by 2 = ");
rightRotate(arr, 2, arr_size);
printArray(arr, 7);
return 0;
}
Solution 2 (Juggling Algorithm):
In this solution besides the rotate the element one by one we will rotate the array in sets. Where the number of sets is equal to GCD of n (array size) and K (position to rotate array elements).
Suppose arr is an integer array and size is 7, we want to rotate it by 2. So here n=7 and k =2 and array elements are {1,2,3,4,5,6,7};
If we calculate GCD of 7 and 2, then it would be 1. So elements will be moved within one set only, we just start with temp = arr[0] and keep moving arr[I+d] to arr[I] and finally store temp at the right place.
#include <stdio.h>
#include <stdint.h>
//Calculate array size
#define ARRAY_SIZE(arr) sizeof(arr)/sizeof(arr[0])
//Calculate the calculateGcd
int calculateGcd(int a, int b)
{
if (b == 0)
{
return a;
}
else
{
return calculateGcd(b, a % b);
}
}
//Function to left rotate array of size n by k
void leftRotate(int arr[], int k, int n)
{
int i, a, b, temp;
// To handle if k >= n
k = k % n;
const int gcd = calculateGcd(k, n);
for (i = 0; i < gcd; i++)
{
/* move i-th values of blocks */
temp = arr[i];
a = i;
while (1)
{
b = a + k;
if (b >= n)
b = b - n;
if (b == i)
break;
arr[a] = arr[b];
a = b;
}
arr[a] = temp;
}
}
//print array elements
void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n\n");
}
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7};
//get array size
int arr_size = ARRAY_SIZE(arr);
printf("Original Array = ");
printArray(arr, arr_size);
printf("Left shift array by 2 = ");
leftRotate(arr, 2, arr_size);
printArray(arr, arr_size);
return 0;
}
Output: 3 4 5 6 7 1 2
Recommended Articles for you:
- Best gift for programmers.
- Best electronic kits for programmers.
- Rearrange array such that elements at even positions are greater than odd in C.
- C program to remove duplicates from sorted array
- Find the Median of two sorted arrays of different sizes using C code.
- C Program to find first and last position of the element in a sorted array
- Write C program to find the missing number in a given integer array of 1 to n
- C program to find the most popular element in an array
- Find the largest and smallest element in an array using C programming.
- C program to find even occurring elements in an array of limited range
- Find sum of all sub-array of a given array.
- C program to segregate even and odd numbers
- Find an element in array such that sum of left array is equal to sum of right array.
- C Program to find the count of even and odd elements in the array.
- Write C program to find the sum of array elements.
