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

## No comments:

## Post a Comment