Rotating an array using Juggling algorithm

Question

I recently learnt about how the Juggling algorithm rotates an array in linear time when I was reading the solution in the Programming Pearls book.

The code to solve it was as follows:

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

I have two questions regarding this algorithm -

1. How does the GCD decide the number of cycles needed to rotate the array?
2. Why is it that once we finish a cycle, we start the new cycle from the next element ie. can't the next element be already a part of a processed cycle?

I feel, I am missing something fundamental regarding the working of GCD, modulus and the cycles.

The following question had an answer to my first question, but still I was not able to understand it.

Juggling algorithm of string rotation

So, it would be helpful if someone can explain it in layman terms and the principle behind how they all gel together to make this algorithm work.

Answer 1

How does the GCD decide the number of cycles needed to rotate the array?

Because the inner loop increments in steps of d, and stops when it gets back to the starting point, i.e. a total span which is some multiple of n. That multiple is LCM(n, d). Thus the number of elements in that cycle is LCM(n, d) / d. The total number of such cycles is n / (LCM(n, d) / d), which is equal to GCD(n, d).

Why is it that once we finish a cycle, we start the new cycle from the next element i.e. can't the next element be already a part of a processed cycle?

No. The inner loop increments in steps of d, which is a multiple of GCD(n, d). Thus by the time we start the i-th cycle, for a hit we'd need (k*GCD + z) % n == i (for 0 <= z < i). This leads to (k*GCD) % n == (i - z). This clearly has no solutions.