Rotating an array using Juggling algorithm

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

Solution 2:

GCD is really an example of the beauty of maths. Sometimes, when you get the thing in your mind, your mind would answer itself for the things it does putting how it happened aside.

Now coming to question, the rotation task, simply could have been worked with a for-loop. Juggling algorithm might have some advantages over it (I didn't find what).

Now coming to the point Why GCD. The GCD gives an exact figure of rotation to be performed. It actually minimizes no of rotations.

For example,

if you want to perform rotation of 30 numbers

with d = 1 the outer loop will be rotating once and inner would rotate 30 times 1*30=30

with d = 2 the outer loop will be rotating twice and inner would rotate 15 times 2*15=30

with d = 3 the outer loop will be rotating thrice and inner would rotate 10 times 3*10=30

So, the GCD Here would ensure the rotations don't exceed the value 30. And as you are getting a number that is divisor of total elements, It won't let skip any element