# Juggling Algorithm for Array Rotation.

Subscribe to my newsletter and never miss my upcoming articles

Hello Everyone!💚

This article is everything you need to know about array rotation. Array Rotation is one of the most important concepts, used in a wide range of problems which includes shifting of elements.

## CONTENTS

### What is array rotation?

By name, we can understand that rotation means simply shifting elements of an array by a specified number of positions. Rotations can be of 2 types: left and right. See below examples to get a clear understanding of what it is.

Left Rotation: Here, k=2 (where k is the number of positions to be shifted left). Right Rotation: Here, k=2 (where k is the number of positions to be shifted right). Did you spot the difference between these two examples? Great! Let's proceed further.😁

### Some of the approaches...

1. By using a temporary array
``````arr[]=[1,2,3,4,5], k=2
1.) storing the elements to be rotated in temp[]
temp[]=[1,2]  //considering left shift
2.) shifting elements to left in arr[]
arr[]=[3,4,5,4,5]
3.)Storing back the elements in temp[]
arr[]=[3,4,5,1,2]
``````
2. By rotating elements one by one
``````arr[]=[1,2,3,4], k=2
//left rotate
1.) [2,3,4,1]
2.) [3,4,1,2]
``````
Other methods include block-swap algorithm, reversal algorithm, juggling algorithm, etc. We know, one code can be written in many ways. But, choosing an optimal code is the ultimate goal. ### Understanding juggling algorithm

• Consider an array of length n=6, k=3 (assume).
 1 2 3 4 5 6
• Consider the greatest common divisor of n,k as g. Divide the array into g sets. Therefore, here g=3 so, sets are {1,2},{3,4},{5,6}.
• Now, rotate the first elements in all sets to left and later followed by the next element rotations till the last element in set gets rotated. 3 2 5 4 1 6 3 4 5 6 1 2

After all rotations, we have obtained the final required array.Now, we are aware of the concept. Let's try to code.😎

### Hands-on coding for left rotation

1. writing a method `gcd(n,k)` to get gcd.
``````int  gcd(int n,int k){
if(n==0){
return k;
}
if(k==0){
return n;
}
if(n>k){
return gcd(n-k,k);
}
else{
return gcd(n,k-n);
}
}
``````
2. After obtaining gcd, we have to write code for shifting corresponding elements in each block.
``````void juggle(int[] arr,int n,int k){
int g=gcd(n,k);
int temp,m,j;
for(int i=0;i<g;i++){
temp=arr[i];
j=i;
while(true){  //true
m=j+k;
if(m>=n){
m=m-n;
}
if(m==i){
break;
}
arr[j]=arr[m];
j=m;
}
arr[j]=temp;
}
}
``````

After all the elements in the blocks(sets) are shifted, the array will be rotated in a way, which satisfies the required output.

Time Complexity: O(N) Space Complexity: O(1)

### An easy method for right rotation

Let us consider the previous example,

 1 2 3 4 5 6

Left Rotation(k=2)

 3 4 5 6 1 2

Right Rotation(k=2)

 5 6 1 2 3 4

Left Rotation(k=4)

 5 6 1 2 3 4

Here, to write a code for right rotation just observe the examples carefully. If you see, we can get the output of the right rotation by considering k=4 for left rotation. Therefore, for right rotation just consider `k=n-k`.

That's it! You have learnt how to juggle arrays😍 ### Comments (5)

Nice, You have explained this so well :)

Hi laasya, great explanation. Can you give little more intuition into why GCD times? how exactly GCD justifies it..