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)

8 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;
    }

  3. Claudio Rodrigues on October 6, 2016 at 1:49 am said:

    // Autor: Claudio C Rodrigues
    // Data: dd/mm/aaaa

    #include
    #include
    #include

    int a[100000];
    int main() {
    int n, d, i;
    /* Read input from STDIN. Rotate array by d elements. Print output to STDOUT */
    scanf(“%d %d”,&n,&d); // n <– number of elem. d <– number of shift lefts
    for(i=0;i<n;++i) scanf("%d",&a[i]); // real elements
    for(i=d;i<n+d;++i) printf("%d ",a[i%n]); // print array rotacionado
    return 0;
    }

  4. raghavendra on October 22, 2016 at 2:21 am said:

    help me, I need a program to shift bot first and second largest element in an max heap

  5. Darpalli Aravind Swami on June 21, 2019 at 4:29 pm said:

    Help me I need a c program for left rotation of an array of size n by d positions

  6. Iswarya on June 25, 2019 at 10:46 am said:

    #include
    void main()
    {
    int n,i,j,k,temp,a[20];
    printf(“enter the n value:”);
    scanf(“%d”,&n);
    printf(“enter the array elements:”);
    for(i=0;i<n;i++)
    {
    scanf("%d",&a[i]);
    }
    printf("enter the rotation:");
    scanf("%d",&k);
    for(i=0;i0;j–)
    {
    a[j]=a[j-1];
    }
    a[j]=temp;
    }
    printf(“right rotated array:”);
    for(i=0;i<n;i++)
    printf("%d ",a[i]);
    }

  7. Pooja Rai on February 2, 2020 at 4:00 pm said:

    this logic can also be used..

    while(d>0){ //d=number of rotations to be
    performed
    cout<<arr[(i+(n-d))%n];
    }

    this piece of code will also print the iterations performed at each step.

Leave a Reply to raghavendra Cancel 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