Problem Statement:

Given a character array of length \(n\), shift it by \(k\) places using at most one additional byte of memory. For example \([1,2,3,4,5]\) shifted by 2 is \([3,4,5,1,2]\).

We approach the problem by trying to shift an array by just one character. Then, a rotation by \(k\) is simply \(k\) rotations by one.

To shift an array by one, we need to ‘bubble-up’ the first element to the very right. That is, \([1,2,3,4,5]\) maps to \([2,3,4,5,1]\). To bubble the element to the right, simply start at the left, and pairwise swap all the neighbouring pars of elements with each other. A swap function takes only an extra byte, but you can use a convoluted method to swap using bitwise xor at no additional extra space cost.

Hence, to shift by one, the code is as follows:

To rotate by \(k\), simply do \(k\) one-rotations:

Note that this is not the optimal solution. We test the proposed solution, and confirm the correctness of the algorithm:

## 0.1 Improvement

We can improve this to \(O(n)\) time as follows. Given an integer \(k\) and a sequence \(s\), split \(s\) into two subsequences \(s = ab\), where \(|a| = k\) – that is, \(a\) is of length \(k\). We require the transformation to \(s' = ba\) which is achieved by seeing that \((a^R b^R)^R = ba\) where \(R\) is the operator that reverses a sequence. With that, we achieve the following algorithm: