# Program to Rotate an Array by N Positions

• Write a program in C to rotate an array by K positions with and without using temporary array.

Given an integer array of size N. We have to shift given array by K positions. Shifting of elements must be in cyclic order.
For Example :
Input Array : 1 2 3 4 5 6 7
K = 3
Output Array : 4 5 6 7 1 2 3

Let inputArray be an integer array of size N and we want to shift inputArray by K positions.

By using a temporary array
Let the temporary array of size N be tempArray.
• Copy first K elements of inputArray(from index 0 to K-1) to tempArray.
• Now, shift remaining elements of inputArray to K positions left.(inputArray[i-K] = inputArray[i]).
• Copy first K elements of tempArray to the end of inputArray.
Time Complexity : O(n)
Space Complexity : O(n)

By shifting all elements one position at a time
1. shiftArrayOnePosition : This function shifts all elements of array by one position in cyclic order.
2. rotateArray : To shift an array bu K positions, this function will call shiftArrayOnePosition function K times.
Algorithm to shift each element of array by one position.
• Store first element of inputArray in a temporary variable(temp = inputArray[0]).
• Starting from inputArray[1], shift all positions to left adjacent index(inputArray[i-1] = inputArray[i]).
• Store temp value at last index of inputArray(inputArray[N-1] = temp).
Time Complexity : O(n)
Space Complexity : O(1)
```#include <stdio.h>

/*
Function to shift array elements by one position
*/
void shiftArrayOnePosition(int *array, int size) {
int i, temp;
/*Save first element in a temporary variable and
shift remaining elements by one index left */
temp = array[0];

for(i = 0; i < size-1; i++) {
array[i] = array[i+1];
}
/* Now put the firt element of
original array to last index */
array[i] = temp;
}

/*
This function shifts array by N positions
*/
void rotateArray(int *array, int size, int N){
int i;
for(i = 0; i < N; i++){
shiftArrayOnePosition(array, size);
}
return;
}

int main(){
int array[10] = {0,1,2,3,4,5,6,7,8,9};
int i;

printf("Original Array\n");
for(i = 0; i<10; i++){
printf("%d ", array[i]);
}
rotateArray(array, 10, 3);

printf("\nRotated Array\n");
for(i = 0; i<10; i++){
printf("%d ", array[i]);
}

return 0;
}
```
Output
```Original Array
0 1 2 3 4 5 6 7 8 9
Rotated Array
3 4 5 6 7 8 9 0 1 2
```

By splitting input Array in blocks and shifting elements in cyclic order
• Find the GCD of N and K. Let the result be G.
• Divide the inputArray into G sets.
• Shift ith element of all sets at a time in cyclic order.
• Continue above step until all elements of set gets shifted.
Time Complexity : O(n)
Space Complexity : O(1)
```#include <stdio.h>

/*
* Function to calculate Greatest Common
* Divisor of two number
*/
int getGcd(int a, int b) {
if (b == 0)
return a;
else
return getGcd(b, a % b);
}

/*
* Function to left rotate arr[] of siz n by d
*/
void rotateArray(int *array, int N, int size) {
int i, j, k, temp, gcd = getGcd(size, N);
/* This loop will run gcd times, in each iteration
it will shift one element of each block to it's
appropriate position */
for (i = 0; i < gcd; i++) {
/* shift ith element of each block */
temp = array[i];
j = i;
while(1) {
k = j + N;
if (k >= size)
k = k - size;
if (k == i) /* one rotation completed */
break;
/*Swap jth element with j+N th element */
array[j] = array[k];
j = k;
}
array[j] = temp;
}
}

int main(){
int array[10] = {0,1,2,3,4,5,6,7,8,9};
int i;

printf("Original Array\n");
for(i = 0; i<10; i++){
printf("%d ", array[i]);
}

rotateArray(array, 3, 10);

printf("\nRotated Array\n");
for(i = 0; i<10; i++){
printf("%d ", array[i]);
}

return 0;
}
```
Output
```Original Array
0 1 2 3 4 5 6 7 8 9
Rotated Array
3 4 5 6 7 8 9 0 1 2
```