# Juggling Algorithm for Array Rotation.

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?
- Some of the approaches...
- Understanding juggling algorithm
- Hands-on coding for left rotation
- An easy method for the right rotation

### 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...

**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]`

**By rotating elements one by one**

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.`arr[]=[1,2,3,4], k=2 //left rotate 1.) [2,3,4,1] 2.) [3,4,1,2]`

### 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

- 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); } }`

- 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π