My interpretation/proof of the Cyclic Replacements Method in Editorial Solution
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 r
**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:\n* The introduction\n* The first attempt of proof which is not rigidly correct.\n* The second attemp of proof which is more comprehensive.\n---\n## Introduction\nI 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.\n\nFirst, I am putting the code directly copied from the editorial solution here for reference:\n```java\npublic class Solution {\n    public void rotate(int[] nums, int k) {\n        k = k % nums.length;\n        int count = 0;\n        for (int start = 0; count < nums.length; start++) {\n            int current = start;\n            int prev = nums[start];\n            do {\n                int next = (current + k) % nums.length;\n                int temp = nums[next];\n                nums[next] = prev;\n                prev = temp;\n                current = next;\n                count++;\n            } while (start != current);\n        }\n    }\n}\n```\nThe main idea is to put each entry(denoted by its index) to its correct position after `k` shifts. \nFirst consider how you would do this in a naive way. (assuming `k = k % n` is already done).\n```java\nfor (int i = 0; i < nums.length; i++) {\n    put nums[i] to position[(i + k) % n] //cyclic shift\n}\n```\nBut this naive way has a problem, when you reach `i + k`, this entry is already gone: overriden by the iteration of `i`.\nTo 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.\n\nThis **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).\n## Proof Attempt 1: intuitive but not really complete\n**Lemma1**: This algorithm visits each entry/index of `nums` exactly once. During the visit, the algorithm shifts the entry to the correct position. \n**Proof**: \n### Case 1: `n % k != 0`\n**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**.\n\nif `n % k != 0`, the outer loop will only execute one iteration(`start == 0`) before the algorithm finisheds.\nIf `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 then`start == 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.\nNow 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). \n\n**Lemma2**: No duplicate indexes will be visited (other than `start`) in each inner-loop. \n**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:\n```\n0 -> 3 -> 6 -> 2 -> 5 -> 1 -> 4 -> 0\n```\nThis is a chain of length 7 (in terms of number of distinct indexes in the chain).\nWe 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:\n```\nstart -> ... -> a -> ... -> a -> ... -> start\nA               B           C           D\n```\nWhere the index `a` is picked twice by the pointer `current`, also `a \u2260 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.\nA 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 \u2260 start`. This is a contradiction.\n**End of proof for Lemma2**\nThus 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.\nI 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.\n\n### Case 2: `n % k == 0`\nFor 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.\nThat is, each `start` visits `n / k` distinct indices.\nThen 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**\n\nWe are now sure that the entire algorithm will visit `n / k * k = n` indices, but are they guaranteed to be distinct?\nYes, 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:\n```\nidx1 = idx2\n(s1 + a * k) % n = (s2 + b * k) % n\n```\nfor 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). \nWe can deduce that\n```\n(s1 - s2) % n = (b - a) * k % n\ns1 - s2 = (b - a) * k + t * n               //for some t\n|s1 - s2| \u2265 k\n```\nBecause \n* if `t != 0`, then `|s1 - s2| \u2265 n > k`; \n* if `t == 0`, then `s1 - s2 = (b - a) * k`, and we know `s1 - s2 \u2260 0`, so `b \u2260 a`, thus we also have `|s1 - s2| \u2265 k`.\n\nThis is a contradiction with the previous conclusion of `start`\'s domain being `0..k-1`.\n\nThus the `n` indices visited in the algorithm will also be distinct.\n**End of Proof for Lemma1**\n\nI think this **lemma 1** is enough for understanding the correctness of this algorithm. There is also a [nice solution](https://discuss.leetcode.com/topic/11349/my-three-way-to-solve-this-problem-the-first-way-is-interesting-java) here using a similar idea. I would learn that one as well if I were you.\n\nHere is a trace to help your understanding:\n<img src="http://i66.tinypic.com/vhb37m.png" width="350">\n\n## Proof Attempt 2: complete and general\nLet\'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.\n<img src="https://www.dropbox.com/s/qe5z20o4xn0d1x2/Screenshot%202018-06-01%2018.23.05.png?raw=1" width="600">\n\nAs 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`. \nIf 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`.\n\nIn the example above where `n,k=7,3`, we have\n```\nL = (7) * 3 = (3) * 7\n```\nThe parens are used to mark the `n` and `k` variables we care about.\n\nFrom 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.\nAnother example: `n,k=10,4`:\n```\n0 -> 4 -> 8 -> 2 -> 6 -> 0\n```\nThis 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:\n```\nL   = (10) * 2 = ((2) * 5) * 2\n    = (4) * 5  = ((2) * 2) * 5\n```\nNote how the GCD is also marked with parens.\n\nNow, 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.\nAt this moment, given the sole input of `n` and `k`, we can tell:\n* how many disjoint chains we have?\n    * why are they disjoint, as in why would there be no duplicates across chains? See the proof for **case 2** in **attempt 1**.\n* how long each of the chain would be?\n\nThese 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](https://discuss.leetcode.com/topic/11349/my-three-way-to-solve-this-problem-the-first-way-is-interesting-java) where GCD calculations are done explicitly is that everything just, happens, and it\'s correct.\n\nNow, look back at the code, you should see that the code is actually doing:\n```\nfor each CHAIN:\n    for each INDEX in this CHAIN:\n        move elements\n```\n**Lemma 3**: each index will be traversed exactly once during the entire outer-loop.\n**Proof**:\nFirst, 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.\nSecondly, from **lemma 1**, we know that each index will be touched no more than once within each inner-loop (chain).\n\nNow, what conclusion do we have by now: each index will be touched *no more than once* in the entire outer-loop.\nThis is not enough, we want *exactly* touched once.\n\nThe 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? \nWell, in the case of `n \u2265 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.\nThis case is not possible because the length of each chain is deterministically calculated as shown above: `chain_len = L / k`:\n```\nL   = (10) * 2 = ((2) * 5) * 2\n    = (4) * 5  = ((2) * 2) * 5\n```\nThe `chain_len` is actually `n / GCD`, somebody else help me prove this please.\nAssume 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.\n**End of proof for lemma3**.\nThe termination of the algorithm also trivially follows from **lemma 3**.
[]