python with two solutions (the second one is a trick, may not be a correct algorithm)
Solution 1: do perm for one time and build the dictionary with num:perm, which can be used for the next loops (if there is)\n\nSolution 2: I check some of array
Solution 1: do perm for one time and build the dictionary with num:perm, which can be used for the next loops (if there is)\n\nSolution 2: I check some of arrays built during perm calculation; find that the first and the last nums never change but the others; we may do only one element calculation and finish at when it is back. It is kind of O(n) complexity?\n```\n    # #Solution 1 (Runtime: 260 ms, faster than 73.57%; Memory Usage: 14.5 MB, less than 18.27%)\n    # def reinitializePermutation(self, n: int) -> int:\n    #     init = [x for x in range(n)]\n    #     nums = [x for x in range(n)]\n    #     numDict = {}\n    #     for x in range(n):\n    #         if nums[x]%2 == 0:\n    #             perm = int(nums[x]/2)\n    #         else:\n    #             perm = int(n/2 + (nums[x]-1)/2)\n    #         numDict[nums[x]] = perm\n    #         nums[x] = perm\n    #     step = 1\n    #     if nums == init:\n    #         return step\n    #     else:\n    #         while nums != init:\n    #             nums = [numDict[x] for x in nums]\n    #             step += 1\n    #         return step\n    \n    \n    #Solution 2 (Runtime: 20 ms, faster than 99.90%; Memory Usage: 14.2 MB, less than 87.10% )\n    def reinitializePermutation(self, n: int) -> int:\n        perm = int(n/2 + (1-1)/2)\n        step = 1\n        if perm == 1:\n            return step\n        else:\n            while perm != 1:\n                if perm%2 == 0:\n                    perm = int(perm/2)\n                else:\n                    perm = int(n/2 + (perm-1)/2)\n                step += 1\n            return step\n```
[]