Java Beats 100% O(1) space, O(N) time, Detail Explanation, Easy to Understand
Inpired by Lee\'s solution. \nAccording to the description, it\'s not hard to find what is the mapping. \nIt\'s mapping the even number to the first part of the
Inpired by [Lee\'s](https://leetcode.com/problems/minimum-number-of-operations-to-reinitialize-a-permutation/discuss/1130534/JavaC%2B%2BPython-6-lines-O(1)-Space) solution. \nAccording to the description, it\'s not hard to find what is the mapping. \nIt\'s mapping the even number to the first part of the permutation to it. \nIf it\'s odd number, map the second part of the permutation to it. \nIf `i % 2 == 0, then arr[i] = perm[i / 2]`  \nIf `i % 2 == 1, then arr[i] = perm[n / 2 + (i - 1) / 2]`\n\nSo there will be no duplicate after each operation. As it\'s firt half => even and second half => odd number mapping. \nFor same number n and same i, for example, `i = 1 and n = 4`, it will be at the same position after the operation given the formula only depends on `i and n`. \n\nNow the problem simplifies as, we don\'t need to care about all other numbers, we only need to focus on one number, which we use number 1 here as `2 <= n <= 1000` , as long as any single number comes back to its original position, it\'s the solution. Proof by contracdtion: if the number 1 comes back to 1, and it\'s not the solution, it will go through the same loop again, then the solution does not exist, which is not the case. \n\n```\npublic int reinitializePermutation(int n) {\n\t// use number 1 as indicator, any other number is fine as long as it\'s smaller than n\n\t// we just need to guarantte it comes back to orginal position\n\tint i = 1, res = 0;\n\twhile (res == 0 || i != 1){\n\t\tif (i % 2 == 0){\n\t\t// map first half to even number\n\t\t\ti /= 2;\n\t\t} else {\n\t\t// map second half to odd number\n\t\t\ti = (n / 2 + (i-1)/2);\n\t\t}\n\t\tres++;\n\t}\n\treturn res;\n}\n```
['Math', 'Java']