- 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.

Space Complexity : O(n)

**By shifting all elements one position at a time**

- shiftArrayOnePosition : This function shifts all elements of array by one position in cyclic order.
- 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.

Space Complexity : O(1)

- 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).

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 i
^{th}element of all sets at a time in cyclic order. - Continue above step until all elements of set gets shifted.

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