leetcode Question: Rotate Array

Rotate Array

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

Hint:

Could you do it in-place with O(1) extra space?

Analysis:

1st solution is to use a temp array.  Space O(n).

e.g. nums = [ 1 2 3 4 5 ], k=2
temp = [4 5 1 2 3]
num = temp


2nd solution is to rotate one position each time and do it k times. Space O(1), but it will exceed the time limit.
e.g. nums = [1 2 3 4 5], k=2
1st iteration:
      nums = [1 1 2 3 4] temp = 5, then nums = [5 1 2 3 4]
2nd iteration:
      nums = [5 5 1 2 3] temp = 4, nums = [4 5 1 2 3]



3rd solution is to rotate k steps once for an element. Space O(1).
e.g. nums = [1 2 3 4 5 6], k=2
1st iteration: starts from nums[i=0], keep rotate nums[i+k] until meet the start position
      nums = [5 2 1 4 3 6]
2nd iteration: starts from nums[i=1]
      nums = [5 6 1 2 3 4]

How to determine the number of iterations?

Use the gcd (greatest common divisor) between n and k. Because we need to find how many "circles" are there in the sequence, one circle is like counting each element nums[i] + k + k + k... and back to nums[i]. If the gcd is 1, which means only one circle will cover all the elements in the sequence, so only 1 iteration is needed.If the gcd is 2, there are 2 circles, so 2 iterations are needed.

Code(C++):

class Solution {
public:
    int gcd(int a, int b){
        if (b==0){
            return a;
        }else{
            return gcd(b, a%b);
        }
    }
    
    void rotate(int nums[], int n, int k) {
        int i,j,tmp,pre;
        k = k%n;
        for (int i=0;i<gcd(n,k);i++){
            pre = nums[i];
            j=i;
            while ((j+k)%n != i){
                tmp = nums[(j+k)%n];
                nums[(j+k)%n] = pre;
                pre = tmp;
                j = (j+k)%n;
            }
            nums[(j+k)%n] = pre;
        }
        
    }
};

Code(Python):

class Solution:
    # @param nums, a list of integer
    # @param k, num of steps
    # @return nothing, please modify the nums list in-place.
    def rotate(self, nums, k):
        
        def gcd(a,b):
            if b==0:
                return a
            else:
                return gcd(b, a%b)
        
        n = len(nums)
        for i in range(gcd(n,k)):
            pre = nums[i]
            j = i
            while (j+k)%n != i:
                nums[(j+k)%n], pre = pre, nums[(j+k)%n]
                j = (j+k)%n
            nums[(j+k)%n] = pre