Rotate an array by d elements

Problem: Write a program that will rotate a given array of size n by d elements.

eg: 1 2 3 4 5 6 7 and d = 3
Output : 4 5 6 7 1 2 3

Method 1:

For rotating the array by d elements, first rotate it by 1. Move a[1] to a[0], a[2] to a[1] and so on.
Repeat the shifting process d times.
In the above example, We get [2, 3, 4, 5, 6, 7, 1] after first rotation, [ 3, 4, 5, 6, 7, 1, 2] after second rotation and [ 4, 5, 6, 7, 1, 2, 3] after third rotation.

// function to rotate array by one shifting all elements one by one
void rotateByOne(int a[], int n)
{
  int i, temp;
  temp = a[0];
  for (i = 0; i < n-1; i++)
     a[i] = a[i+1];
  arr[i] = temp;
}

// repeat above function d times to rotate array
void rotateArray(int a[], int n, int d)
{
  int i;
  for (i = 0; i < d; i++)
    rotateByOne(a, n);
}
 

Time complexity: O(n*d)

Method 2: Using temp array

Input a[] = [1, 2, 3, 4, 5, 6, 7], d = 3 and n =7
(1) Store first d elements in a temporary array
temp[] = [1, 2, 3]
(2) Shift rest of the array
a[] = [4, 5, 6, 7, 6, 7]
(3) Store back the d elements
a[] = [4, 5, 6, 7, 1, 2, 3]

Time Complexity: O(n), Space Complexity: O(d)

Method 3: Using reversal algorithm

Using reversal algorithm, lets assume array as combination of 2 arrays say A1A2.
First, reverse the A1 then reverse A2. then reverse complete set A1A2.

Lets try to understand this with an example.

For a[] = [1, 2, 3, 4, 5, 6, 7], d = 3 and n = 7
A1 = [1, 2, 3] and A2 = [4, 5, 6, 7]
Reverse A1, we get A1′B = [3, 2, 1, 4, 5, 6, 7]
Reverse A2, we get A1′B1′ = [3, 2, 1, 7, 6, 5, 4]
Reverse complete set, we get (A1′B1′)’ = [4, 5, 6, 7, 1, 2, 3]

// reverse array from start to end
void reverse(int a[], int start, int end)
{
  int i;
  int temp;
  while(start++ < end--)
  {
    temp = a[start];
    a[start] = a[end];
    a[end] = temp;
  }
}

// function that will rotate array by d elements
void rotateArray(int a[], int d, int n)
{
  reverse(a, 0, d-1);
  reverse(a, d, n-1);
  reverse(a, 0, n-1);
}

Time Complexity: O(n)

2 Thoughts on “Rotate an array by d elements

  1. i think its a better algorithm..

    for i =0 to n/2-1
    swap(a[n/2-i],a[n/2]+i)

  2. #include
    #include
     
    int main()
    {int n;
    printf("Enter size of array\n");
    scanf("%d",n);
    int B[n];
    int A[n] ;
    int k,i,j,l;
    i=0;j=0;
    printf("Enter values\n");
    for(l=0;l < n;l++)
    {
        scanf(%d,A[l]);
    }
    printf(Enter number of element you want to rotate\n);
    scanf(%d,k);
     
    while(i < k)
    {
    B[n-k+i]=A[i];
     
    i++;
    }
    j=n-k;
     
    while(i < n)
    {
        B[n-k-j]=A[i];
        i++;
        j–;
    }
     
    for(i=0;i < n;i++)
    {
        printf(%d\n,B[i]);
    }
    return 0;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation