# My c++ solution, o(n)time && o(1)space

• ``````class Solution {
public:
void rotate(int nums[], int n, int k) {
int nowIndex = 0, nextIndex;
int tmp1, tmp2 = nums[0];
for(int j=0,i=0; j<n; j++){
tmp1 = tmp2;
nowIndex = (k + nowIndex) % (n);
tmp2 = nums[nowIndex];
nums[nowIndex] = tmp1;
if(nowIndex == i) {
nowIndex = ++i;
tmp2 = nums[nowIndex];
}
}
}
};``````

How to change [0,1,2,3,4,5,6] to [4,5,6,0,1,2,3] by k = 3?

We can change by following rules: [0]->[3], [1]->[4], [2]->[5], [3]->[6], [4]->[0], [5]->[1], [6]->[2]

Other cases are the same.

To solve this problem, we should know the following two facts:

1. We must do exactly n assigned-steps to finish the target.

see the two figures below. On the right side of each figure shows the same process as left side. The total step is just the number of edges.

2. We can obtain several self-closed circles when we do the operation.

By figure we can clearly see it. Each time when we exchange values among a circle, there is no relationship with other circles.Done with this one, we move to another circle.

``````class Solution {
public:
void rotate(int nums[], int n, int k) {

if(n == 0)return;
k = k % n;

//initialize
int i = 0;
int nowIndex = 0;
int tmp = nums[0],stmp;

//exactly n steps, n times loop
for(int j = 0; j < n; j++)
{
//next index to exchange
nowIndex = (nowIndex + k) % n;

//exchange
stmp = nums[nowIndex];
nums[nowIndex] = tmp;
tmp = stmp;

//finish a circle,move to another circle
if(nowIndex == i)
{
nowIndex = ++i;
tmp = nums[nowIndex];
}
}
}
``````

};

• you light me!!!

• nowIndex should less than n

• Good job. And nowIndex should less than n

• Thanks for your question. I think no need to consider nowIndex is less than n or not. Since you may think "nowIndex = ++i" maybe larger or equal than n, but it is impossible. Because nowIndex is the first position in one circle assignment.The index must appear at front of the array.

• [1] k=1 nowIndex can be 1 and nums[nowIndex] out of range

• Thx.Although nums[nowIndex]may out of range, no influence on final result. Besides this, for k>=n,we can always make k = k%n, and if k==0 , array doesn't change. Add this special case may avoid this problem.

• yes. And your explanation is excellent.

• Thanks a lot for the explanation! But could you tell me, how many "loops" can be in an array? Or,to put it another way, what is the maximum value of the variable i? And how does this value depend on the length of an array and on the value of k? For example,I see,that when k is even there are 2 loops, when odd - 1.Is there any particular rule?

• (k + nowIndex) % (n) this is to keep nowindex less than n