## 2016/03/26

### 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);
}
```