Right shift Array elements K positions

problem

Given an array with size N, shift the elements K position right. 

Solution

brutal force solution is to move all the elements one position right at a time, put the last position to the first position. Repeat K times, the time cost is O(NK). The space cost is O(1).

we can use a K sized array to store K values, then shift k elements right. Finally put the last K values to the first K values. The time cost is O(N), the space cost is O(K).

We can use math to solve it. LS -> SL

(LbarSbar)bar = SL

so we reverse [0, N - K - 1], then reverse [N - K, N - 1], then reverse the [0, N - 1].

/*
Given a size N array, move the elements K positions right.
For example:
abcd1234 -> 1234abcd

dcba 4321 -> 1234abcd

abc123xyz -> xyzabc123

321cba zyx -> xyz abc123

abcd123 -> 123abcd

dcba 321 -> 123 a bcd
*/

class KRightShift {
  public static void shift(int[] a, int k) {//4
    int N = a.length;
    //0, 1, 2, 3, 4, 5, 6, 7, 8, 9
    for(int i = 0; i < N; i = i + k) { //8
      int lo = i; //8
      int hi = Math.min(N - 1, i + k - 1);//min(9, 11) = 9
      while(lo < hi)
        exch(a, lo++, hi--); //98
    }
    int lo = 0;   //5
    int hi = N - 1;  //4
    while(lo < hi)
      exch(a, lo++, hi--);
  }
  public static void main(String...args) {
    int[] a = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    shift(a, 4);
    for(int i: a) {
      System.out.print(i + " ");
    }
  }
  private static void exch(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
  }
}

The time cost is O(N), the space cost is O(1).