## # Array Rotation In-Place

• Suppose we are given an array of n integers and we have to rotate it by k positions to the left with space complexity of O(1) i.e. within the same array (in-place).
• If we will shift elements one by one it will become hard to keep tack of all elements without using additional space.

• So we will divide the array into sets/cycles where the number of sets will depend on the value of n and k.

• `Number of sets = gcd( n, k )` where gcd is greatest common divisor of n & k.

• And we will shift every element in a set k places to the left by using the formula

`A[j] = A[ ( j + k ) % n]`

• So there will be two nested loops where the outer loop will run for the number of sets and the inner loop with shift elements of a set k positions to the left.

• Let outer loop be from `i=0 to i < gcd(n,k)` i.e for the number of sets.

• Inside the inner loop we will shift the elements k positions to the left for each set i.e starting for i=0.

1. We will take a variable `j` for the inner loop and make `j = i`
2. We will copy the value of first element of the set in a temporary varivale "temp"
3. Then we will calculate `d = (j + k) % n`
4. And make `A[j] = A[d]`
5. Then we will move j to the index of the shifted element by making `j = d`
6. And we will repeat the steps 2 to 5 until `j == i`, i.e. when `j == i` we will break out of the inner loop.
• After the inner loop ends we will copy the value in temp at index `j` i.e `A[j] = temp`

• And we will repeat the steps for every set.

• Suppose we are given this array of 9 elements i.e n=9 and we have to rotate it by 3 positions i.e. k=3.

• Then gcd of 9 & 3 will be 3, therefore we will divide this array into 3 sets and perform shift operation on elements of each set as follows:

### # Source Code - C++

``````#include <iostream>

using namespace std;

int gcd(int a, int b)
{
if(b==0)
return a;
else
return gcd(b, a%b);
}

void ArrayRotate (int A[], int n, int k)
{
int d=-1,i,temp,j;
for(i=0;i<gcd(n,k);i++)
{
j=i;
temp=A[i];
while(1)
{
d=(j+k)%n;
if(d==i)
break;
A[j]=A[d];
j=d;
}
A[j]=temp;
}
}

void displayArray(int A[],int n)
{
int i;
for(i=0;i<n;i++)
cout<<A[i]<<" ";
cout<<"\n";
}

int main()
{
int n,i,k;
cout<<"Enter size of the Array\n";
cin>>n;
int A[n];
cout<<"Enter Array elements\n";
for(i=0;i<n;i++)
cin>>A[i];
cout<<"Enter the value of k\n";
cin>>k;
displayArray(A,n);
ArrayRotate(A,n,k);
displayArray(A,n);
return 0;
}
``````

Time Complexity : O(n)

Space Complexity : O(1)