# Rotate an Array

This post deals with the question of how to rotate an array?

### Rotate an Array problem Statement :

Given an array ,we need to rotate the array the specified number of times. Array rotation can be done in 2 ways.

### Rotate an Array example:

### Rotate an Array Solution:

### Method 1:

This is the simplest way to solve the problem.

**Algorithm:**

- Store the first “d” elements in a temp array.
- Shift the elements of the array to the right or the left.
- Store the “d” elements back in the array.

Here is the working code:

#include <bits/stdc++.h> using namespace std; /*Function to rotate arr[] of size n by d*/ void RotateArray(int arr[], int d, int n) { int temp[d]; /*Storing d elements in temp array*/ for(int i=0;i<d;i++) temp[i]=arr[i]; /*Shifting rest of array*/ for(int j=0;j<n-d;j++) arr[j]=arr[j+d]; /*Storing back d elements*/ for(int k=n-d,i=0;k<n;k++,i++) arr[k]=temp[i]; } /* Function to print the array */ void printArray(int arr[], int size) { for(int i = 0; i < size; i++) cout<<arr[i]<<" "; } /* Driver program to test above functions */ int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7}; printArray(arr,7); RotateArray(arr, 3, 7); cout<<"\nArray after Rotation is:\n"; printArray(arr, 7); return 0; }

**Output:**

1 2 3 4 5 6 7 Array after Rotation: 4 5 6 7 1 2 3

**Time Complexity : O(N)**

**Auxiliary space:O(d)**

### Method 2:

We rotate the array one by one by storing the first element in temp variable and move A[1] to A[0]…and temp to A[n-1].

- Rotate the array by 1 element.
- Repeat the above process “d” times.

We are using left rotation in the solution.

#include <bits/stdc++.h> using namespace std; /*Function to rotate an array k times*/ void RotateArray(int A[], int d, int n) { for (int i = 0; i < d; i++) { int j, temp; /*Rotating array by one step*/ temp = A[0]; for (j = 0; j < n-1; j++) A[j] = A[j+1]; A[j] = temp; } } /*Function to print the array */ void printArray(int A[], int size) { for(int i=0; i < size; i++) cout<<A[i]<<" "; } /*Driver program to test the above functions*/ int main() { int A[] = {10, 20, 30, 40, 50, 60, 70}; printArray(A,7); RotateArray(A, 4, 7); cout<<"\nArray After Rotation \n"; printArray(A, 7); return 0; }

**Output:**

10 20 30 40 50 60 70 Array After Rotation 50 60 70 10 20 30 40

**Time Complexity:** **O(N*d)**

**Space Complexity:O(1)**

### Method 3:

Also known as **the juggling algorithm** this method extends method 2 and is used to rotate an array.

The algorithm divides the array into some blocks and then it swaps the elements present in the array in the intervals of length of GCD(n,d).

Instead of moving one by one, the array is divided in different sets where number of sets is equal to GCD of n and d and the elements within sets are moved.

If GCD is 1, then elements will be moved within one set only, we just start with temp = arr[O] and keep moving arr[i+d] to arr[i] and finally store temp at the right place.

**Algorithm:**

- Find GCD of “n” and “d”.Let it be “g”.
- Array is divided into consecutive sets containing g elements.
- The first element of each set is rotated once.
- Then the second element and so on.

**Example:**

Let the array be arr[]={1,2,3,4,5,6}. Here n=6 and d=2. GCD(6,2)=2 Array after first set elements are rotated. arr[]={3,2,5,4,1,6} Array after second set elements are rotated. arr[]={3,4,5,6,1,2}

Here is the working code in c++:

#include <bits/stdc++.h> using namespace std; /*Function to get gcd of a and b*/ int gcd(int a,int b) { if(b==0) return a; else return gcd(b, a%b); } /*Function to rotate arr[] of size n by d*/ void RotateArray(int arr[], int d, int n) { int i, j, k, temp; for (i = 0; i < gcd(d, n); i++) { /* move i-th values of blocks */ temp = arr[i]; j = i; while(1) { k = j + d; if (k >= n) k = k - n; if (k == i) break; arr[j] = arr[k]; j = k; } arr[j] = temp; } } /* Function to print the array */ void printArray(int arr[], int size) { for(int i = 0; i < size; i++) cout<<arr[i]<<" "; } /* Driver program to test above functions */ int main() { int arr[] = {10, 20, 30, 40, 50, 60, 70}; printArray(arr,7); RotateArray(arr, 2, 7); cout<<"\nArray after Rotation\n"; printArray(arr, 7); return 0; }

**Output:**

10 20 30 40 50 60 70 Array after Rotation 30 40 50 60 70 10 20

**Time Complexity:O(N)**

** Space Complexity:O(1)
**It takes no extra space and its the most efficient algorithm to rotate an array.