Juggling Algorithm

Suppose we have an array, let’s call it arr. The following algorithm is implemented in the language C++.

int arr[]={4,5,6,1,2,3};

Now, the question is to rotate the array arr, which is currently is of size 6 by x elements.

Let’s assume x to be 3. Hence, we have to rotate the array by 3 to the left.

You can skip Part 1, if you are able to visualize the Problem

Part 1

If we rotate array by 1 element.
The new array will be 
5,6,1,2,3,4
Note how 4 appears at the back.
If we again rotate by 1 element 
New array will be 
6,1,2,3,4,5
Let’s do it one last time, so that now we can have a clear visualization and compare it with orgioriginal array
new array      ->1,2,3,4,5,6
original array ->4,5,6,1,2,3

Part 2
You may skip this part, if you implemented the naive approach.

Think for a approach, for 5 minute and then look at the solution.

Approach one

We can make a temporary array and complete our task.
What we have to do here is.
Store the first three element or the x element in an temporary array.
Shift the array towards left.
and then copy the element stored in temporary array back to our original array.

Wait, this approach is exactly similar to the approach of swapping two elements.

int temp=a;
a=b;
b=a;

Now since, we are only storing the x elements, the space complexity will be O(x) and Time complexity O(n). Since n-d elements will be shifted inside the original array and d elements have to copied back to the original array.
So n-d+d=n

Approach 2

What if I tell in our first approach, instead of taking an array of size d.
You are just given a single integer temp variable to rotate the element.

Well, In that case you have to store the first element in the temp and rotate the array by 1 to the left and store the temp variable back in the array.

So though our space complexity is O(1) but the time complexity is 0(n*d)

Approach 3

This is the most interesting algorithm, which is called the Juggling Algorithm.

The algorithm says we divide the array in different sets.

Of what size though?
Number of set is equal to gcd(size of the array, x),
where x is the value by which we have to rotate the array

Then, we move the element within these number of sets.

Let's again imagine the algorithm
4,5,6,1,2,3
Now, we as our algorithm says we have take calculate the gcd(n,x) which is 3.
Hence, we are dividing the array into 
Set 1-> 4,5,6
Set 2-> 1,2,3

Note, now we have to move elements between sets.
Imagine this, we now have two hands and we are juggling balls from one hand to another. Here the balls represent elements in array and hands represent different sets we have just assumed in our array.

So how that would go, we first throw Element 1 in the Set 1 and throw element 4 in the Set 2.
New array — 1,5,6,4,2,3

Let’s move ahead, now we throw element 2 in the Set 1 and throw element 5 in the set 2.
New array — 1,2,6,4,5,3

The Last juggle- we throw element 3 in the Set 1 and throw element 6 in the set 2.
New array — 1,2,3,4,5,6

Here, we will be using too loops and there’s one temporary variable which stores the starting element of the array

How many times did we juggle?

3

If you are still not able to visualise, Here’s little experiment for you.

Take 3 balls in each hand number them all.

Start juggling from one hand to another and do it exactly for 3 cycle. At the end, look at the numbered balls in each hand.

Let’s continue
So we have to run the outer loop for gcd(n,x)
What about the inner loop. Will talk about it.

We are defining a temp variable which stores the start element of the inner loop and store it index in variable j.
Inside the while loop
We have define k as j+x.

Getting it?
So if the element is at position 1, we have to juggle it with the element which is at position k+d in the array.
Like, if the array is 4,5,6,1,2,3
and our first element is 4 at position 0

We have to juggle it with the element 1 which is at position 0 (position of 4)+ x(x=3). hence, resultant position is 3.

Now, Understanding the condition inside the inner loop.

So if(k≥n) where n is the size of the array.
Meaning, there might be cases we have to rotate the array by 10 even though our size of array is 3, anything else then 10.
In that case we have to keep decreasing i.e that is subtracting the value of 3 from 10. Until it falls in the range of index of array and we don’t get arrayoutofindex

Condition 2.
Imagine someone tells you to juggle the balls by one cycle.
How you gonna do?
You name a ball A and start juggling keeping the ball in right hand and if the ball A returns to the right hand again you stop.
So the condition here is

if(k==i) Stop

Last statement inside
we juggle the element from set 2 to set 1.
How we write that

arr[j]=arr[k]

and now we move to set 2.
How to do ?
j=k.

If any other set exist after 2, it will juggle that is inner loop will continue

Outer Loop
and thats my friend is the last juggle.

Just after we have exited from the inner loop, theres one final statement to write.

Since we know after exiting from the loop, we have juggle the ball from set 2 to set 1.
But have juggled the ball back to set 2.
Nope, we didnt.
Hence, we write arr[j]=temp;

Here, we have only two sets, and by 2 sets I means 2 hands.
So we have to juggle from hand 2 to hand 1 and finally hand 2 to hand 1.
Sounds fair. Hence, we are using break condition inside the loop to terminate the inner loop.

/*Function to left rotate arr[] of siz n by d*/
void leftRotate(int arr[], int x, int n)
{
  int i, j, k, temp;
  for (i = 0; i < gcd(x, n); i++)
  {
    /* move i-th values of blocks */
    temp = arr[i];
    j = i;
    while(1)
    {
      k = j + x;
      if (k >= n)
        k = k - n;
      if (k == i)
        break;
      arr[j] = arr[k];
      j = k;
    }
    arr[j] = temp;
  }
}

Source: Programming Pearls Book

The following algorithm has a time complexity of O(n) and space complexity of O(1)

Thank you everyone.
This was my attempt the explain the code.

Hope you are able to understand the logic.