Shift an array

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:

// Shift cs by one element to the left. The remaining goes to the back
// Runs in O(n) where n is the lenght of cs
public static void shift_one(char[] cs){
  for(int i = 0; i < cs.length - 1; i++){
    swap(cs,i,i+1);
  }
}

  // Swapping with no extra storage.
public static void swap(char[] s, int pos1, int pos2){
  s[pos1] = (char) (s[pos1] ^ s[pos2]);
  s[pos2] = (char) (s[pos1] ^ s[pos2]);
  s[pos1] = (char) (s[pos1] ^ s[pos2]);
}

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

// Rotate the char array cs by k elements by rotating by 1, k times
public static void inplace_rotate(char[] cs, int k){
  for(int i = 0; i < k; i++){
    shift_one(cs);
  }
}

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

char[] c1 = "12345678".toCharArray();
inplace_rotate(c1,3);
System.out.println(c1);

45678123

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:

// Reverses the array `a` between bounds [l,r]
static void reverse(int[] a, int l, int r){
  if(r < l) return;
  int mid = l + (r-l)/2;
  for(int i = l; i <= mid; i++){
    swap(a, i, r+l-i);
  }
}

// Rotates array `a` by `k` elements to the left.
// Pre: 0 <= k <= a.length
static void rotateK(int[] a, int k){
  reverse(a, 0, k-1);
  reverse(a, k, a.length-1);
  reverse(a, 0, a.length-1);
}