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
Posted by
Labels: ,