Rotating an array right by k moves every element k slots to the right and wraps the ones that fall off the end back to the front. The first ideas cost extra time or a second array. Two tricks do it in place with one spare variable and about n moves: three reversals, and following the cycles of the rotation.
After a right rotation by k, the element at index i sits at index (i + k) mod n. Rotating by n puts everything back where it started, so only k mod n matters. Both first attempts work. One moves far too much, the other needs a second array.
How to read this: Each lettered box is one element, named by where it started. Watch the boxes slide; the small numbers underneath are slot positions.
Try this: Drag k up to 7 with Shift by one and compare the write count to Copy.
Shift by one touches every element on every pass, so it costs n·(k mod n) writes, close to n² when k is near n. Copying is linear but holds a second array of n slots. Labs 2 and 3 get both: linear time and one spare slot.
Call the first n − k elements A and the last k elements B. The array reads A B and the answer is B A. Reversing the whole array puts the blocks in the right order, each one backwards. Two more reversals turn each block around again. Each reversal walks two pointers inward and swaps.
Try this: Press Step and watch the amber lo and hi pointers walk toward each other, swapping as they go.
Reading a sequence backwards starts at its end, so the last block comes out first, reversed. Reversing a block twice restores it, so phases 2 and 3 undo the backwards order inside each block without moving the boundary.
A reversal of m elements makes ⌊m/2⌋ swaps. The total ⌊n/2⌋ + ⌊k/2⌋ + ⌊(n−k)/2⌋ is exactly n when k and n − k are both even, and n − 1 otherwise.
Element i belongs at slot (i + k) mod n. Pick one up, drop it where it belongs, pick up whatever was there, and keep going. Every write puts an element in its final slot, so the rotation takes exactly n writes and one carried value. The catch: the chain can come back to its start before it has visited every slot.
How to read this: Each circle is a slot, numbered outside the ring. Arrows show where its element must go (k slots clockwise). The amber dot is the element being carried to its new slot.
Try this: Press 12, 5 (one big loop), then 12, 8 (four small loops) and compare.
From slot s the chain visits s, s + k, s + 2k, … mod n. Those are exactly the slots that leave the same remainder as s when divided by g = gcd(n, k). So each cycle has n / g slots, there are g cycles, and starting from slots 0 … g − 1 covers them all. When g = 1, one cycle visits every slot.
Euclid's algorithm finds g in a few divisions. It's the same one from 003 · Number theory.