Clear cyclic replacement Java solution with proof, O(N) in time, O(1) in space
Clear cyclic replacement solution with proof\n## Intuition\nAssume k = k % n.\n\nImagine we have an array A = [0, 1, 2, 3, 4, 5, 6] (n = 7) and need to shift it
# Clear cyclic replacement solution with proof\n## Intuition\nAssume `k = k % n`.\n\nImagine we have an array `A = [0, 1, 2, 3, 4, 5, 6]` (n = 7) and need to shift it right by `k = 3` by HAND.\n\nWhat I would do is start from index 0, **hold** `A[0]=0` in hand, go to next index `(0 + k) % n = (0 + 3) % 7 = 3`, and swap `A[3]` with what I hold in hand, repeat this step until all elements are moved. The indexes of elements traversed form a closed chain `0 -> 3 -> 6 -> 2 -> 5 -> 1 -> 4 -> 0`, which has 7 elements, equal to array length.\n\nHowever, if `n` and `k` are not mutually prime, we may return to start position before moving all elements, forming a closed chain with elements fewer than `n`, e.g. `n = 6, k = 4 => 0 -> 4 -> 2 -> 0`, this chain only has `L1 = 3` elements. To move all elements, we need to start from index 1 and traverse another chain `1 -> 5 -> 3 -> 1`, which contains `L2 = 3` different elements. In total we moved `L1 + L2 = 3 + 3 = 6 == n` elements, and each element moved only once. \n\nThe general procedures are:\n1. start from index `start = 0` (actually can be any other index)\n2. cyclically shift element at index `(start + m * k)` right by `k` until reaching start again, forming a closed chain\n3. shift `start` by 1, repeat step 1 and 2 until all elements moved.\n\n## Solution\n```\nclass Solution {\n    // Cyclic replacement\n    public void rotate(int[] nums, int k) {\n        if (nums == null || nums.length <= 1 || k <= 0) {\n            return;\n        }\n        \n        int n = nums.length;\n        int step = k % n;\n        int count = 0; // count of elements moved to target position\n        for (int start = 0; start < n; start++) {\n            // Cyclically move each element until returning to start position and forms \n            // a closed chain\n            int hold = nums[start];\n            int p = start;\n            do {\n                p = (p + step) % n;\n                // swap hold and nums[p]\n                int tmp = hold;\n                hold = nums[p];\n                nums[p] = tmp;\n                count++;\n            } while (p != start);\n            \n            if (count == n) {\n                break;\n            }\n        }   \n    }\n}\n```\n\n## Proof\n### Lemme 1: Each closed chain has same length `L = n / gcd(n, k)`\n**Proof**:\n`lcm`: least common multiple\n`gcd`: greatest common divisor\n\nAccording to the chain definition, a chain with index `start -> (start + k) % n -> (start + 2k) % n -> ... -> (start + Lk) % n` closes when chain ends at start index, i.e. `(start + Lk) % n == start`, i.e. when `Lk == tn`, where `t` is a positive integer as small as possible. In other words:\n\n`Lk == lcm(n, k)` => `L = lcm(n, k) / k`\n\nAccording to the [relation between lcm and gcd: `gcd(a,b) * lcm(a, b) = a * b`](https://math.stackexchange.com/questions/470807/prove-that-gcdm-n-times-mboxlcmm-n-m-times-n), we have:\n\n`L = lcm(n, k) / k = (n * k / gcd(n, k)) / k = n / gcd(n, k)`\n\nFor example:\n* `n = 7, k = 3` => `L = 7 / gcd(7, 3) = 7 / 1 = 7`\n* `n = 6, k = 4` => `L = 6 / gcd(6, 4) = 6 / 2 = 3`\n\nLemme 1 indicates each inner loop ends after `L = n / gcd(n, k)` steps.\n\n### Lemme 2: For any index `0 <= i < j < gcd(n, k)`, chains starting from `i` and `j` are mutually exclusive.\n**Intuitive Proof**:\nThanks to @kafa321:\nIf two chains intercept, after intersection point, since both chains advance by `k` every step, esentially they are the same chain.\n\n**Strict mathmatical proof by contradiction**\nAssume two chains does intercept at index `p` after `x` steps from `i` and `y` steps from `j`, i.e.\n`p = (i + x * k) % n == (j + y * k) % n`\n=> `(j - i + (y - x) * k) % n == 0`\n=> `(j - i) - (x - y) * k = tn`\n=> `j - i = (x - y) * k + tn`\n=> `j - i = (x - y) * gcd(n, k) * (k / gcd(n, k)) + t * gcd(n, k) * (n / gcd(n, k))`\n=> `j - i = gcd(n, k) * ((x - y) * (k / gcd(n, k)) + t * (n / gcd(n, k)))`\n=> `j - i = M * gcd(n, k), M is an integer`\n\nHowever, `0 < j - i < gcd(n, k)`, so there exists no valid `M`, assumption is invalid.\n\n### Conclusion\nBased on Lemma 1 and 2, we have proven that the cyclic replacement algorithem has following properties:\n* Each inner loop moves `L = n / gcd(n, k)` unique indexes (according to chain definition, no duplicate indexes other than start position is allowed in a closed chain).\n* Outer loop iterates start position from `0` to `gcd(n, k) - 1`, execute inner loop `gcd(n, k)` times\n* All indexes moved in those `gcd(n, k)` inner loops are mutually exclusive, in total `n / gcd(n,k) * gcd(n, k) = n` unique indexes have been moved. \n\n\n\n
[]