title: Rotating an array using Juggling algorithm
body: <p>I recently learnt about how the <strong>Juggling algorithm</strong> rotates an array in linear time when I was reading the solution in the Programming Pearls book. </p>
  
  <p><strong>The code to solve it was as follows:</strong></p>
  
  <pre><code>/*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 &lt; gcd(d, n); i++)
    {
      /* move i-th values of blocks */
      temp = arr[i];
      j = i;
      while(1)
      {
        k = j + d;
        if (k &gt;= n)
          k = k - n;
        if (k == i)
          break;
        arr[j] = arr[k];
        j = k;
      }
      arr[j] = temp;
    }
  }
  </code></pre>
  
  <p>I have two questions regarding this algorithm - </p>
  
  <ol>
  <li>How does the GCD decide the number of cycles needed to rotate the
  array?</li>
  <li>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?</li>
  </ol>
  
  <p>I feel, I am missing something fundamental regarding the working of <strong>GCD</strong>, <strong>modulus</strong> and the <strong>cycles</strong>. </p>
  
  <p>The following question had an answer to my first question, but still I was not able to understand it.</p>
  
  <p><a href="https://stackoverflow.com/questions/21910835/juggling-algorithm-of-string-rotation">Juggling algorithm of string rotation</a></p>
  
  <p>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.</p>