RotateArrayOPT [source code]

public class RotateArrayOPT {
static
/******************************************************************************/
public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        int count = 0;
        for (int start = 0; count < nums.length; start++) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % nums.length;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while (start != current);
        }
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        RotateArrayOPT.Solution tester = new RotateArrayOPT.Solution();
        int[][] inputs = {
            {1,2,3,4,5,6,7}, {3}, {5,6,7,1,2,3,4},
            {1,2,3,4,5,6,7,8,9,10}, {3}, {8,9,10,1,2,3,4,5,6,7},
            {1,2,3,4,5,6}, {2}, {5,6,1,2,3,4},
            {1}, {0}, {1},
            {1,2}, {3}, {2, 1},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            int[] nums = inputs[3 * i];
            int k = inputs[1 + 3 * i][0];
            String expected = Printer.array(inputs[2 + 3 * i]);
            System.out.println(Printer.seperator());
            Printer.openColor("magenta");
            System.out.print(Printer.array(nums) + " AND " + k);
            Printer.closeColor();
            tester.rotate(nums, k);
            String output = Printer.array(nums);
            System.out.print(" -> " + output);
            Printer.openColor(output.equals(expected) ? "green" : "red");
            System.out.println(", expected: " + expected);
            Printer.closeColor();
        }
    }
}

这个是editorial3的解. 看起来有点复杂;

这个算法乍一看确实不是很好理解, 但是自己打印几个trace看看, 好像还是能看出门道的;

这个算法editorial给出的名字叫做cyclic replacement; 不过上面对于这个算法给出的解释其实是很糟糕的;

注意看这两个case, 分别是这个算法的两种情况:

1 2 3 4 5 6 7  AND 3  
start: 0, prev: 1, count: 0  
1 2 3 4 5 6 7   
1 2 3 1 5 6 7   
1 2 3 1 5 6 4   
1 2 7 1 5 6 4   
1 2 7 1 5 3 4   
1 6 7 1 5 3 4   
1 6 7 1 2 3 4   
5 6 7 1 2 3 4   
 -> 5 6 7 1 2 3 4 , expected: 5 6 7 1 2 3 4  

 1 2 3 4 5 6  AND 2  
start: 0, prev: 1, count: 0  
1 2 3 4 5 6   
1 2 1 4 5 6   
1 2 1 4 3 6   
5 2 1 4 3 6   
start: 1, prev: 2, count: 3  
5 2 1 4 3 6   
5 2 1 2 3 6   
5 2 1 2 3 4   
5 6 1 2 3 4   
 -> 5 6 1 2 3 4 , expected: 5 6 1 2 3 4

第一种情况其实是一个比较普遍的情况: 大多数时候start是没有移动的机会的, 直接一个start位置的iteration里面就可以把count攒满了;

但是也有特殊情况, 比如这里的第二种情况: n % k == 0. 在这种情况下, 一个start(0)是没有办法攒够count的, 这个时候current会重新走到start的位置, 但是这个时候count却没有攒满, 那么我们就走start的下一个element: the element following nums[start].

这个算法在editorial里面的描述比较乱, 所以我以为作者估计水平一般, 就当做是一个一般性的不怎么厉害的算法啊来看, 但是实际上这个算法还是很聪明的;

这个算法最后做到的其实就是保证每一个数字至少遍历一次. 只要每一个数字遍历一次, 那么就能保证每个数字都被移动到了自己的correct position (+k 然后mod n).
这个算法如果你用最naive的思路去做, 其实就是从第一个开始, 从左到右, 全部都cyclic shift k steps就行了, 但是这个有一个问题, 你必须要保存目标位置的entry, 那么如果你直接从左到右做, 这个保存的数据结构的space是肯定超过O(1)的.
他这个算法最后就是有一个优化, 通过一个类似于chain一样的操作, 让所有的entry的shift公用一个temp, 那么最后就是O(1)的space了;

那么他这个算法是怎么做到遍历所有的entry一次的呢?

• 假如说n % k != 0, 那么在start等于0开始的这个iteration, 一般count就达到了, 也就是只有一个iteration(外层). 首先你要确定, 在这个情况下, current是不可能回到start的, 不然mod k就不可能是0了; 同样的, 在current变化的过程中, 所有的值都是distinct的, 任何一个重复都代表mod k == 0; 那么在这个情况下, 只要我们保证完成了n个shift, 也就是n个current的取值, 我们就可以保证所有的entry都被遍历到了一次: 因为总共就这么多distinct entries/indices.
• 假如说n % k == 0, 那么对于每一个start, 我们其实是完成n / k个值. 总共有多少个start可以取呢(从0开始, 一个一个上涨)? 首先明确一点, 对于不同的start的iteration, 各自的n / k个index是互相不重合的. 这个可以用类似一层楼一层楼的概念来理解. 如果非要数学上证明也不难, 首先要明确, 我们最多有k个start可以取: 0..k-1, 因为无论不同的start的iteration中间是否有重复, 一旦数到n就肯定结束;
  假设start1 + a * k == start2 + b * k, 并且start1 != start2, 那么肯定有|start1 - start2| >= k, 这个是不可能的, 因为start的domain就是0..k-1;
  所以最后还是会遍历n个distinct indices.

这个算法背后体现的设计思想其实还是很聪明的. 而且可以说是是一个优化得到的结果, 并不是类似reverse那个做法.

discussion上有一个家伙写了一个更复杂的思路, 但是跟这个思路是类似的:

public class Solution {  
    public void rotate(int[] nums, int k) {  
        if(nums.length <= 1){  
            return;  
        }  
        //step each time to move  
        int step = k % nums.length;  
        //find GCD between nums length and step  
        int gcd = findGcd(nums.length, step);  
        int position, count;  

        //gcd path to finish movie  
        for(int i = 0; i < gcd; i++){  
            //beginning position of each path  
            position = i;  
            //count is the number we need swap each path  
            count = nums.length / gcd - 1;  
            for(int j = 0; j < count; j++){  
                position = (position + step) % nums.length;  
                //swap index value in index i and position  
                nums[i] ^= nums[position];  
                nums[position] ^= nums[i];  
                nums[i] ^= nums[position];  
            }  
        }  
    }  

    public int findGcd(int a, int b){  
        return (a == 0 || b == 0) ? a + b : findGcd(b, a % b);  
    }      
}

这个是他自己的解释:

Here use a example input array [1,2,3,4,5,6,7,8] (n = 8) to explain:

1.suppose k = 3:

GCD = gcd(3,8) = 1, which means there is only one path.

Count = (n / GCD) - 1 = 7, which means we need 7 swaps to finish the path. (actually for a path have x element, we need x - 1 swaps)

Then we can simulate the process of the algorithm,

path0(each time swap index0 element and indexPosition element):

[1,2,3,4,5,6,7,8] (position = 3) -> [4,2,3,1,5,6,7,8] (position = 6) -> 7,2,3,1,5,6,4,8 -> 2,7,3,1,5,6,4,8 -> 5,7,3,1,2,6,4,8 -> 8,7,3,1,2,6,4,5 -> 3,7,8,1,2,6,4,5 -> [6,7,8,1,2,3,4,5] -> finished, total 7 times swap. Final result [6,7,8,1,2,3,4,5]

2.suppose k = 2:

Similary, GCD = 2, which means there are 2 paths.

count = 3, which means we need 3 swaps to finish each path.

Give the process:

path0(swap index0 and position element):

1,2,3,4,5,6,7,8 -> 3,2,1,4,5,6,7,8 ->5,2,1,4,3,6,7,8 -> [7,2,1,4,3,6,5,8] -> path0 finished

Then we continue processing path1(swap index1 and position element):

7,2,1,4,3,6,5,8 -> 7,4,1,2,3,6,5,8 -> 7,6,1,2,3,4,5,8 ->[7,8,1,2,3,4,5,6] -> path1 finished -> all path finished we get the result [7,8,1,2,3,4,5,6]

具体怎么搞的没认真看了, 这个题目花的时间也比较多了. 反正知道大体意思就行了;
注意他这里计算GCD的这个算法, 这个要稍微记忆一下, 好像是一个什么有名的算法: Euclidean algorithm.

我在discussion上面贴了一个对这个算法的证明, 扔在bear了;

2018-06-01 15:13:14
算了, 我这个证明最后居然很多人喜欢, 所以就放在这里了:

I find the Cyclic Replacements method in the editorial solution quite clever and spent some time learning it. On the other hand, I am not quite satisfied with the explanation and proof provided there. Thus I am elaborating on my way of relating to this algorithm here.

First, I am putting the code directly copied from the editorial solution here for reference:

public class Solution {  
    public void rotate(int[] nums, int k) {  
        k = k % nums.length;  
        int count = 0;  
        for (int start = 0; count < nums.length; start++) {  
            int current = start;  
            int prev = nums[start];  
            do {  
                int next = (current + k) % nums.length;  
                int temp = nums[next];  
                nums[next] = prev;  
                prev = temp;  
                current = next;  
                count++;  
            } while (start != current);  
        }  
    }  
}

The main idea is to put each entry(denoted by its index) to its correct position after k shifts.
First consider how you would do this in a naive way. (assuming k = k % n is already done).

for (int i = 0; i < nums.length; i++) {  
    put nums[i] to position[(i + k) % n] //cyclic shift  
}

But this naive way has a problem, when you reach i + k, this entry is already gone: overriden by the iteration of i.
To avoid this problem, we could buffer nums[i + k] before we shift nums[i], but such a modification, albeit feasible for the problem, would fail the O(1) space requirement: you need O(n - k) space to buffer the entries.

This Cyclic Replacements solution, on the other hand, overcomes this problem: only one buffer variable prev is shared for all shifts of all n elements(although the code declares new current, prev, etc. in each iteration, JVM optimization can handle that, or you can always just make these variables global to the loop block anyway).

Lemma: This algorithm visits each entry/index of nums exactly once. During the visit, the algorithm shifts the entry to the correct position.
Proof:

Case 1: n % k != 0

if n % k != 0, the outer loop will only execute one iteration(start == 0) before the algorithm finisheds.
If n % k != 0, the inner do-while loop will only execute when count == n. Consider what this inner loop does: for example, in the case of [1,2,3,4,5,6,7] and k = 2, it essentially does something like 1 -> 3, 3 -> 5, 5 -> 7, 7 -> 2, 2 -> 4, 4 -> 6, 6 -> 1, and thenstart == current and count == n == 7. We will then have to try to get to the second iteration of the outer loop, which fails due to count == n. Thus the outer loop only executes one iteration.
Now let's abstract: when n % k != 0, we start from [0] and in this one iteration, we can shift all n elements (to its perspectively correct position). This is because each current in the do-while loop will all be distinct indices (other than the last one that reaches start and ends the loop). This is proven by contradiction: suppose there are two iterations (of the inner do-while) where we have the same current. Then

current = (current + k) % n (done t times for some t) would end up at current again.  
(current + t * k) % n = current

Since current < n, we have

current + t * k % n = current  
t * k % n = 0

I think this can actually leads to n % k = 0 now (I tried to give a rigid explanation but my math education is just too ancient to recall. I do find it possible to do if expressing n as a * k + b with b < a and prove, but you get the idea.)

This is a contradiction with this case's assumption.

Thus conclusion: during the n iterations of the inner do-while loop, current never duplicates itself.
From this conclusion we know that, when the inner and outer loop exits, we must have already iterated all n indices of nums: there are only n distinct ones, and our iteration never duplicates itself.

Case 2: n % k == 0

For each start value of the outer loop, it is obvious to see that the inner loop does n / k iterations, visiting one distinct indice in each iteration.
That is, each start visits n / k distinct indices.
Then we increment start. How many values of start can we have (or what is the number iterations of the outer loop)? It has to be k, because in each outer loop, count get incremented n / k no matter what (even if there are duplicates across different outer loop iterations/start values, which we shall debunk later). So the domain of start is 0..k-1. marker here

We are now sure that the entire algorithm will visit n / k * k = n indices, but are the guaranteed to be distinct?
Yes, and this is proven by contradiction. Suppose there exists two indices idx1 and idx2, each corresponding to start == s1 and start == s2 in the outer loop. Then we have:

idx1 = idx2  
(s1 + a * k) % n = (s2 + b * k) % n

for some a and b. We also know that s1 != s2 (it's trivially obvious that you can't have duplicate indices within the same outer iteration/startvalue).
We can deduce that

(s1 - s2) % n = (b - a) * k % n  
s1 - s2 = (b - a) * k + t * n               //for some t  
|s1 - s2| ≥ k

Because

• if t != 0, then |s1 - s2| ≥ n > k;
• if t == 0, then s1 - s2 = (b - a) * k, and we know s1 - s2 ≠ 0, so b ≠ a, thus we also have |s1 - s2| ≥ k.

This is a contradiction with the previous conclusion of start's domain being 0..k-1.

Thus the n indices visited in the algorithm will also be distinct.
End of Proof

I think this lemma is enough for understanding the correctness of this algorithm. There is also a nice solution here using a similar idea. I would learn that one as well if I were you.

Here is a trace to help your understanding:

但是这个好像是有问题的:

ibici 0 an hour agoReport
I don't think the "Case 1: n%k != 0" part of the proof is correct. I believe you are stating that, in this case, we visit every index once before cycling back to our start. As far as I know, this is not true for any case in which n%k != 0 and both n and k are even; all multiples tk are even and thus all tk mod n are even, so you can see that we'd return to our start after exhausting all even indices (assuming 0 indexing).

For example, when n = 10 and k = 4: (0 -> 4), (4 -> 8), (8 -> 2), (2 -> 6), (6 -> 0).

Of course the algorithm still works, since starting again from index 1 would then take care of all odd indices. However I've yet to find a complete proof. I think the only part I'm missing is how to show that we'll cycle back to 0 before cycling back to one of the indices reached after wrapping around past 0.

他说的好像是有道理的, 我重新思考一下我这个证明哪里有问题;

仔细看了一下, 他的观点是正确的, 在case1, 我只证明了一个inner loop里面走过的所有的index都是distinct, 但是我没有证明所有的N个都会被走遍;

重新思考了一下这个过程:

所以基本上理解之前discuss看到那个解法为什么要算GCD了; 这个是有原因的;

我的分类方法实际上不对, 正确的分类方法应该是考虑是否有大于1的GCD; 包括n % k == 0这个情况, 实际上对应的就是GCD=k的情况; 而在(10, 4)这样的情况, GCD=2也超过1, 最后实际上outer loop执行次数也超过一次; 所以这个GCD应该是这个思路的关键;

在之前那个discuss解法的帖子里面, 有这样一个说法:

leetcode.com/problems/rotate-array/discuss/54289/My-three-way-to-solve-this-problem-the-first-way-is-interesting(JAVA)/55998

zwangbo 982 April 27, 2015 8:22 PMReport
Detail explain of method 1:

Here use a example input array [1,2,3,4,5,6,7,8] (n = 8) to explain:

1.suppose k = 3:

GCD = gcd(3,8) = 1, which means there is only one path.

Count = (n / GCD) - 1 = 7, which means we need 7 swaps to finish the path. (actually for a path have x element, we need x - 1 swaps)

Then we can simulate the process of the algorithm,

path0(each time swap index0 element and indexPosition element):

[1,2,3,4,5,6,7,8] (position = 3) -> [4,2,3,1,5,6,7,8] (position = 6) -> 7,2,3,1,5,6,4,8 -> 2,7,3,1,5,6,4,8 -> 5,7,3,1,2,6,4,8 -> 8,7,3,1,2,6,4,5 -> 3,7,8,1,2,6,4,5 -> [6,7,8,1,2,3,4,5] -> finished, total 7 times swap. Final result [6,7,8,1,2,3,4,5]

2.suppose k = 2:

Similary, GCD = 2, which means there are 2 paths.

count = 3, which means we need 3 swaps to finish each path.

Give the process:

path0(swap index0 and position element):

1,2,3,4,5,6,7,8 -> 3,2,1,4,5,6,7,8 ->5,2,1,4,3,6,7,8 -> [7,2,1,4,3,6,5,8] -> path0 finished

Then we continue processing path1(swap index1 and position element):

7,2,1,4,3,6,5,8 -> 7,4,1,2,3,6,5,8 -> 7,6,1,2,3,4,5,8 ->[7,8,1,2,3,4,5,6] -> path1 finished -> all path finished we get the result [7,8,1,2,3,4,5,6]

但是这个只是描述了过程, 并没有解释为什么, 比如(10, 2)的时候, 我们就是有2个path;

想了一些时间, 最后有如下改动: 主要改动是case1这里, 然后重新加了一个attempt2, 用新的角度来理解; 读的时候可以跳着看:

Caveat at 2018-06-01 16:23:20: it was recently pointed out that my orriginal formulation is appealing yet not really sufficient for the proof of the method. I revised the post so that I provide a revised version of the proof. Yet, I want to retain the original version, which is not strictly correct. The three sections below corresponds to:

• The introduction
• The first attempt of proof which is not rigidly correct.
• The second attemp of proof which is more comprehensive.

---

Introduction

I find the Cyclic Replacements method in the editorial solution quite clever and spent some time learning it. On the other hand, I am not quite satisfied with the explanation and proof provided there. Thus I am elaborating on my way of relating to this algorithm here.

First, I am putting the code directly copied from the editorial solution here for reference:

public class Solution {  
    public void rotate(int[] nums, int k) {  
        k = k % nums.length;  
        int count = 0;  
        for (int start = 0; count < nums.length; start++) {  
            int current = start;  
            int prev = nums[start];  
            do {  
                int next = (current + k) % nums.length;  
                int temp = nums[next];  
                nums[next] = prev;  
                prev = temp;  
                current = next;  
                count++;  
            } while (start != current);  
        }  
    }  
}

The main idea is to put each entry(denoted by its index) to its correct position after k shifts.
First consider how you would do this in a naive way. (assuming k = k % n is already done).

for (int i = 0; i < nums.length; i++) {  
    put nums[i] to position[(i + k) % n] //cyclic shift  
}

But this naive way has a problem, when you reach i + k, this entry is already gone: overriden by the iteration of i.
To avoid this problem, we could buffer nums[i + k] before we shift nums[i], but such a modification, albeit feasible for the problem, would fail the O(1) space requirement: you need O(n - k) space to buffer the entries.

This Cyclic Replacements solution, on the other hand, overcomes this problem: only one buffer variable prev is shared for all shifts of all n elements(although the code declares new current, prev, etc. in each iteration, JVM optimization can handle that, or you can always just make these variables global to the loop block anyway).

Proof Attempt 1: intuitive but not really complete

Lemma1: This algorithm visits each entry/index of nums exactly once. During the visit, the algorithm shifts the entry to the correct position.
Proof:

Case 1: n % k != 0

Caveat: the proof for this case is incorrect, or at least incomplete. If you are not curious how it is incorrect, you can skip this part. The key error I made is I only proved that no duplicate index is visited during one inner-loop, but I did not prove only one inner-loop will be executed.

if n % k != 0, the outer loop will only execute one iteration(start == 0) before the algorithm finisheds.
If n % k != 0, the inner do-while loop will only terminate when count == n. Consider what this inner loop does: for example, in the case of [1,2,3,4,5,6,7] and k = 2, it essentially does something like moving values (not indexes) in this way: 1 -> 3, 3 -> 5, 5 -> 7, 7 -> 2, 2 -> 4, 4 -> 6, 6 -> 1, and thenstart == current and count == n == 7. We will then have to try to get to the second iteration of the outer loop, which fails due to count == n. Thus the outer loop only executes one iteration.
Now let's abstract: when n % k != 0, we start from [0] and in this one iteration, we can shift all n elements (to its perspectively correct position). This is because each current in the do-while loop will all be distinct indices (other than the last one that reaches start and ends the loop).

Lemma2: No duplicate indexes will be visited (other than start) in each inner-loop.
Proof: This is proven by contradiction. Now, for convenience, let's consider the chain of index movements rather than the chain of value movements. For the instance of n=7, k=3, we have:

0 -> 3 -> 6 -> 2 -> 5 -> 1 -> 4 -> 0

This is a chain of length 7 (in terms of number of distinct indexes in the chain).
We start from start, then move current from there, till current reaches start again. What we want to prove is, during this process, current never duplicates itself before it reach the final start. Suppose for the sake of contradiction that it did, then we have a chain like:

start -> ... -> a -> ... -> a -> ... -> start  
A               B           C           D

Where the index a is picked twice by the pointer current, also a ≠ start (otherwise the inner-loop would have terminated at the first a). No a or start is included in any of the three ... segment WLOG.
A trivial way to prove this is that, by the above assumptions, the BC segment has no start, which means, you start from a, you will reach a before reaching a start. But looking at the CD segment, you will have another conclusion: starting from a, you will reach start before reaching a, where a ≠ start. This is a contradiction.
End of proof for Lemma2
Thus concludes my attempt for this case. Note that this case's proof is incomplete in that I proved that no duplicate indexes shall be reached in one inner-loop. But I did not prove that only one inner-loop will execute in this case: in fact, that is a false claim. As pointed out by @ibici.
I could add on more augments to this proof but @ibici 's advice made me rethink about my classification of the two cases here and I eventually see how it is not a good choice. In attempt 2, I will try to provide the proof in a better way.

Case 2: n % k == 0

For each start value of the outer loop, it is obvious to see that the inner loop does n / k iterations, visiting one distinct indice in each iteration.
That is, each start visits n / k distinct indices.
Then we increment start. How many values of start can we have (or what is the number iterations of the outer loop)? It has to be k, because in each outer loop, count get incremented n / k no matter what (even if there are duplicates across different outer loop iterations/start values, which we shall debunk later). So the domain of start is 0..k-1. marker here

We are now sure that the entire algorithm will visit n / k * k = n indices, but are they guaranteed to be distinct?
Yes, and this is proven by contradiction. Suppose there exists two indices idx1 and idx2, each corresponding to start == s1 and start == s2 in the outer loop. Then we have:

idx1 = idx2  
(s1 + a * k) % n = (s2 + b * k) % n

for some a and b. We also know that s1 != s2 (otherwise there is nothing to prove because lemma 2 will guarantee no duplicate within a single inner-loop).
We can deduce that

(s1 - s2) % n = (b - a) * k % n  
s1 - s2 = (b - a) * k + t * n               //for some t  
|s1 - s2| ≥ k

Because

• if t != 0, then |s1 - s2| ≥ n > k;
• if t == 0, then s1 - s2 = (b - a) * k, and we know s1 - s2 ≠ 0, so b ≠ a, thus we also have |s1 - s2| ≥ k.

This is a contradiction with the previous conclusion of start's domain being 0..k-1.

Thus the n indices visited in the algorithm will also be distinct.
End of Proof for Lemma1

I think this lemma 1 is enough for understanding the correctness of this algorithm. There is also a nice solution here using a similar idea. I would learn that one as well if I were you.

Here is a trace to help your understanding:

Proof Attempt 2: complete and general

Let's just see what's happening with a concrete example where n,k = 7,3. Note that from now on all chains/movements are described in terms of indexes rather than values.

As the length of the chain grows, think carefully when would we actually stop? Yes, we would stop when we reached a length L such that L is a multiple of both n and k. To be more accurate, we stop when L is the LCM of n and k.
If the chain started from somewhere like 1 rather than 0, the end result is actually similar, L will always be an LCM and thus a multiple of n.

In the example above where n,k=7,3, we have

L = (7) * 3 = (3) * 7

The parens are used to mark the n and k variables we care about.

From the lemma2 proved in attempt 1, we already know that within one chain, which corresponds to one inner-loop (in that the chain terminates when the first duplciate is reached, which is start), there is no other duplicate index than start. But how long can this chain be? Of course, it can't exceed n: you only have n distinct indexes. In the example above, the first chain (corresponds to start=0) has length chain_len=n=7, which triggers count=n to terminate the outer-loop immediately.
Another example: n,k=10,4:

0 -> 4 -> 8 -> 2 -> 6 -> 0

This chain is only of length 5, and we have n=10, so in the end we need two separate chains, corresponding to two inner-loop executions, to traverse all n indexes. We have:

L   = (10) * 2 = ((2) * 5) * 2  
    = (4) * 5  = ((2) * 2) * 5

Note how the GCD is also marked with parens.

Now, compare the two cases, you should see how LCM and GCD plays a part in this algorithm. We first find the GCD of n and k. Then we can calculate L, which is the LCM, then we can divide it by k, then we have the length of this chain.
At this moment, given the sole input of n and k, we can tell:

• how many disjoint chains we have?
  • why are they disjoint, as in why would there be no duplicates across chains? See the proof for case 2 in attempt 1.
• how long each of the chain would be?

These information are not explicitly utilied in the code, but is helpful for understanding the correctness of the algorithm overall. The beauty of this cyclic replacement code as compared to this solution where GCD calculations are done explicitly is that everything just, happens, and it's correct.

Now, look back at the code, you should see that the code is actually doing:

for each CHAIN:  
    for each INDEX in this CHAIN:  
        move elements

Lemma 3: each index will be traversed exactly once during the entire outer-loop.
Proof:
First, each index will belong to exactly one of the disjoint chains. This derives naturally from how we proved the chains to be disjoint in the first place.
Secondly, from lemma 1, we know that each index will be touched no more than once within each inner-loop (chain).

Now, what conclusion do we have by now: each index will be touched no more than once in the entire outer-loop.
This is not enough, we want exactly touched once.

The outer loop will only terminate when count=n which means we visited all n indexes, which are guaranteed to be distinct from above discussion. Does this statement suffice?
Well, in the case of n ≥ 10, what if we had three inner-loops each contributing 4, 4, 4 to count? In this case, chain_len=4 and in the end we will have count=12>n to terminate the outer-loop.
This case is not possible because the length of each chain is deterministically calculated as shown above: chain_len = L / k:

L   = (10) * 2 = ((2) * 5) * 2  
    = (4) * 5  = ((2) * 2) * 5

The chain_len is actually n / GCD, somebody else help me prove this please.
Assume this is right, then it is clear that chain_len can divide into n, and the case of n,chain_len=10,4 is impossible. Ruling out that possibility, the outer-loop's termination iff exactly n distinct indexes visited is enough to justify the lemma and the algorithm: n is a multiple of chain_len, we will have exactly n=count in the end. All distinct, so each index touched exactly once.
End of proof for lemma3.
The termination of the algorithm also trivially follows from lemma 3.

Problem Description

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.

[show hint]

Related problem: Reverse Words in a String II

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Difficulty:Easy
Total Accepted:130.5K
Total Submissions:534K
Contributor: LeetCode
Companies
microsoft bloomberg
Related Topics
array
Similar Questions
Rotate List Reverse Words in a String II

Hint:
Could you do it in-place with O(1) extra space?
Related problem: Reverse Words in a String II