[Java/C++/Python] 6 lines, O(1) Space
Here is the solution you are waiting for.\nYou need to follow the solution one by one.\nLet me add more explanation meanwhile.\n\n\n# Solution 1: Simulate the w
Here is the solution you are waiting for.\nYou need to follow the solution one by one.\nLet me add more explanation meanwhile.\n<br>\n\n# **Solution 1: Simulate the whole array**\nJust do what the statements says,\nand compare if it equals to the initial state.\n\nAt most `n` permuation in the process,\neach list is size of `n`.\n\nI don\'t give the prove here for the above analysis,\nbacause it\'s not my point in this post.\nThe prove is obvious if you get the last soluiton.\n\nTime `O(n^2)`\nSpace `O(n)`\n\n**Python**\n```py\n    def reinitializePermutation(self, n):\n        A, init = range(n), range(n)\n        res = 0\n        while res == 0 or A != init:\n            A = [A[i / 2] if i % 2 == 0 else A[n / 2 + (i - 1) / 2] for i in xrange(n)]\n            res += 1\n        return res\n```\n<br>\n\n\n# **Solution 2: Simulation an index**\nFind the inverse path of `i`.\n\nTime `O(n)`\nSpace `O(1)`\n\n**Java**\n```java\n    public int reinitializePermutation(int n) {\n        int res = 0, i = 1;\n        while (res == 0 || i > 1) {\n            if (i < n / 2)\n                i *= 2;\n            else\n                i = (i - n / 2) * 2 + 1;\n            res++;\n        }\n        return res;\n    }\n```\n**C++**\n```cpp\n    int reinitializePermutation(int n) {\n        int res = 0, i = 1;\n        while (res == 0 || i > 1) {\n            if (i < n / 2)\n                i *= 2;\n            else\n                i = (i - n / 2) * 2 + 1;\n            res++;\n        }\n        return res;\n    }\n```\n**Python**\n```py\n    def reinitializePermutation(self, n):\n        res, i = 0, 1\n        while res == 0 or i > 1:\n            if i < n / 2:\n                i *= 2\n            else:\n                i = (i - n / 2) * 2 + 1\n            res += 1\n        return res\n```\n\n# **Solution 3: Simulation an index again**\nWe can find that we are keep doing `i *= 2` each time,\nand we mod `n - 1` actually.\nSo there won\'t be duplicate loop.\n\nTime `O(n)`\nSpace `O(1)`\n\n**Java**\n```java\n    public int reinitializePermutation(int n) {\n        int res = 0, i = 1;\n        while (res == 0 || i > 1) {\n            i = i * 2 % (n - 1);\n            res++;\n        }\n        return res;\n    }\n```\n**C++**\n```cpp\n    int reinitializePermutation(int n) {\n        int res = 0, i = 1;\n        while (res == 0 || i > 1) {\n            i = i * 2 % (n - 1);\n            res++;\n        }\n        return res;\n    }\n```\n**Python**\n```py\n    def reinitializePermutation(self, n):\n        res, i = 0, 1\n        while res == 0 or i > 1:\n            i = i * 2 % (n - 1)\n            res += 1\n        return res\n```\n<br>
[]