Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming / 4 / c / i / Solution

Write the segment as $AB$, where $|A|=n-k$ and $|B|=k$. The desired array rotation is $BA$. Reverse each block, then the whole segment:The state changes are $AB\to A^{R}B\to A^R{B}^R\to BA$, using the list reversal identity supplied in the paper and reversal being an involution. Three reversals implement the right rotation in $O(n)$ time and $O(1)$ auxiliary space. The initial return covers empty and identity rotations.