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

  1. What is array rotation?
  2. Some of the approaches...
  3. Understanding juggling algorithm
  4. Hands-on coding for left rotation
  5. 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).

left rotate.PNG

Right Rotation: Here, k=2 (where k is the number of positions to be shifted right).

right rotate.PNG

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.

    juggling-point.PNG

Understanding juggling algorithm

  • Consider an array of length n=6, k=3 (assume).
123456
  • 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.

    juggling-step-1.PNG

325416

juggling-step-2.PNG

345612

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,

123456

Left Rotation(k=2)

345612

Right Rotation(k=2)

561234

Left Rotation(k=4)

561234

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๐Ÿ˜ juggle

Apoorv Tyagi's photo

Nice, You have explained this so well :)

Jatin Rao's photo

Awesome Article Laasya! Thanks for sharing ๐Ÿ˜€

Sai Laasya Vabilisetty's photo

Thank you Jatin๐Ÿ˜Š