# Shift an array

#### Posted on August 3, 2013

##### Last updated on November 22, 2013

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:

Markdown SHA1: 9c9716b5b3406355fbf4478684059198bec58b0e