Array rotation

Problem: left-rotate an array of k positions in place, in linear time and constant auxiliary space.

Solution: If k=1, then we can save the first element in a temporary variable, write in each position, except the last one, the value in the subsequent position, and, finally, write the temporary variable in the last position.

If k>1, we can use the same approach several times for different subsets (not subarrays!) of the array.
Assume that n is the length of the array and k<n (otherwise, we can set k=k%n).
We can save the first element in a temporary variable.
Then, starting from position p=0, we can write in that position the value in position (p+k)%n. Then set p=(p+k)%n and repeat until (p+k)%n is equal to 0.
When  (p+k)%n is 0, in p we write the temporary variable, because in 0 we previously wrote the value in position p+k.
If k and n are co-prime, this approach enables to scan all the array (i.e., (p+k)%n becomes equal to 0 after n-1 iterations). In fact, being p=(l-1)*k, we have that (l*k)%n is 0 only if l is a multiple of n, when gcd(k,n)=1. Thus, p=0 when l=0 (at the beginning) and then when l becomes equal to n (i.e., after a complete scan).
Instead, if n and k are not co-prime, being nc=gcd(n,k)>1, after n/nc-1 iterations (p+k)%n will become 0. Therefore, not all the elements can be rotated in this way, but only n/nc.
However, if set p=1, and we iterate again until (p+k)%n is equal to 1, we can rotate other n/nc elements.
We can repeat this process nc times, setting the initial value of p to 0,1,...,nc-1, thus completing the rotation of all the elements of the array.

A Java implementation is given in the following.

  
public int gcd(int a, int b) {
    if (b==0) {
        return a;
    }
    return gcd(b, a%b);
}

public <T> void rotateArray(T[] a, int k) {
    k = k % a.length;
    int numberOfCycles=gcd(a.length, k);
    int lengthOfCycles=a.length/numberOfCycles;
    for (int i = 0; i < numberOfCycles; i++) {            
        T temp = a[i];
        int p = i;
        for (int j = 0; j < lengthOfCycles-1; j++) {
            a[p%a.length] = a[(p + k)%a.length];
            p+=k;
        }
        a[p%a.length] = temp;
    }
}

Another nice solution is obtained by first inverting the subarray consisting of the first k elements, then then subarray consisting of the last n-k elements, and finally inverting the whole array.
Each element with index i<k after the first inversion will be in position k-i-1, and after the third inversion in position n-1-k+i+1=n-k+i. Each element with index i≥k after the second inversion will be in position n-1-i+k, and after the third inversion in position n-1-n+1+i-k=i-k. The implementation of this algorithm is much simpler than the previous one.

public <T> void invertSubarray(T[] a, int lo, int hi) {
    while (lo < hi) {
        T temp = a[lo];
        a[lo] = a[hi];
        a[hi] = temp;
        lo++;
        hi--;
    }
}

public <T> void rotateArray(T[] a, int k) {
    k = k % a.length;
    invertSubarray(a, 0, k-1);
    invertSubarray(a, k, a.length-1);
    invertSubarray(a, 0, a.length-1);
}