4
$\begingroup$

We are given an array A of size n and we have to rotate it in left direction by d positions. So e.g. if A = {1, 2, 3, 4, 5, 6, 7} then for d = 2, the resultant rotated array is {3, 4, 5, 6, 7, 1, 2}.

One algorithm which does this goes as follows:

  1. Reverse A[0..d-1] (0-indexing)
  2. Reverse A[d..n-1]
  3. Reverse A[0..n-1]

These three steps surprisingly rotate the array correctly. What is the math behind this algorithm? Why does it give a correct solution? It feels magical to me. I am not able to put up a formal proof of its correctness.

$\endgroup$
2
$\begingroup$

Here is a proof by picture, which follows the steps of the algorithm: $$ 0,\ldots,d-1,d,\ldots,n-1 \\ d-1,\ldots,0,d,\ldots,n-1 \\ d-1,\ldots,0,n-1,\ldots,d \\ d,\ldots,n-1,0,\ldots,d-1 $$ You can easily turn this into a formal proof by giving a formula for the permutation after each step, which you can easily prove correct.

$\endgroup$
  • $\begingroup$ This is a good starting point but not sure how to give formula for the permutation? $\endgroup$ – Navjot Waraich Aug 12 '18 at 14:04
  • $\begingroup$ Take it as an exercise. Your formula could involve two separate cases. $\endgroup$ – Yuval Filmus Aug 12 '18 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.