## 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