# Rotate array

First problem in “Cracking the Coding interview” tutorial on HackerRank is to rotate array to the left.

The solution is easy: calculate new index and copy-paste everything from original array to a newly created empty one that is then returned. We can even use `System.arraycopy` to speed up copy process.

But that requires O(n) extra memory. This problem could be solved with O(1) memory.

I already knew the solution (general approach, but not implementation) and it took me ~15 minutes to write algorithm down. However it was buggy and I wasn’t able to find the bug during test run.

After about 25 minutes debugging the problem was discovered.

Optimal solution is to pick number, remember its index and then repeat following n times:

• Compute new index of picked number
• Remember number at this new index
• Set picked number at this new index
• Set remembered number to picked number

It works but corner case exists where it fails. Namely if length of array is divisible by # of steps (k) (without remainder). In that case our replacements will go in loops never touching all elements. (Try to run this algorithm on `1234` with `k=2`).

There is a nice addition to steps described above that fixes that problem:

• If we completed “replacement loop” (inserted number to index we started from) — increment index by 1

The only question remains is “how to detect that loop is completed?”. In my original version it was done with condition `i % k == 0` which wasn’t correct: in `123456` and `k = 2` we’ll do shift 3 times (when `k == 0,2,4`) while we need it 2 times (when `k == 0,3`). The correct condition is `i % (arr.length / k)`.