title: How can I cyclically shift an array without additional heap memory?
body: <p>How can I write a function <code>shift(int* arr, int k)</code> cyclically shift an array by some integer k? I cannot say "malloc" memory from the heap.</p>
  
  <p>For instance, using pseudocode, <code>shift([1, 2, 3, 4], 2)</code> returns <code>[3, 4, 1, 2]</code>, and <code>shift([3, 1, 5, 5], 103)</code> returns <code>[1, 5, 5, 3]</code>. I have tried using modulus to achieve this effect, as shown in this Java program, in which I basically iterate through half of the array and swap values.</p>
  
  <pre><code>public static int* shift(int* arr, int k) {
    int half_array_len = arr.length / 2;
    for (int i = 0; i &lt; half_array_len; ++i) {
      // Swap!
      int newIndex = (i + k) % arr.length;
      int temp = arr[i];
      arr[i] = arr[newIndex];
      arr[newIndex] = arr[i];
    }
    return arr;
  }
  </code></pre>
  
  <p>However, I believe that this function only works for even-lengthed arrays.</p>
  
  <p>How can I implement <code>shift</code> for arrays of any length? Answers can be in any language you want (Java, C++, <a href="http://esolangs.org/wiki/Ook!" rel="nofollow">Ook Ook!</a>, etc.).</p>