python LCM
Approach\nwe need to divide the numbers to chains.\neach chain is the following loop:\nindx1->indx2->..indx1\nthe -> means step, indx i moves to indx j in a sin
# Approach\nwe need to divide the numbers to chains.\neach chain is the following loop:\nindx1->indx2->..indx1\nthe -> means step, indx i moves to indx j in a single step.\nFor example for n = 10:\nchain 1: 0->0 len=1\nchain 2: 9->9 len=1\nchain 3: 2->1->5->7->8->4->2 len=6\nchain 4: 3->6->3 len = 2\n\nin each chain after len(chain) operations all the indexes of the chain will go back to their places.\nSo after we divided to chains all we have to do is to find the LCM of the chains. and this is the answer.\n\nfinding LCM is classic problem with  a well know solutions and probably already built in on python 3, but I wrote in python 2 so I copied some classic algortyhm for LCM. \n\n# Complexity\n- Time complexity:\nits O(n) for the part of finding the chains\n\nand the gcd part is something like log(n) for a pair, so n*log(n) for the whole list. \n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution(object):\n    def reinitializePermutation(self, n):\n        """\n        :type n: int\n        :rtype: int\n        """\n        chains_lenghts = self.get_chains_length(n)\n        return self.LCM(chains_lenghts)\n    \n    def advance(self, indx, n):\n        return (indx / 2) + ((n / 2) * (indx % 2))\n\n    def get_chains_length(self, n):\n        remaining, res = set(range(n)), []\n        while len(remaining) > 0:\n            curr, cnt = remaining.pop(), 0\n            while True:\n                cnt += 1\n                curr = self.advance(curr, n)\n                if curr not in remaining:\n                    break\n                remaining.remove(curr)\n            res.append(cnt)\n        return res\n\n    def LCM(self, numbers):\n        res = 1\n        for num in numbers:\n            res = (res * num) / self.gcd(res, num)\n        return res\n    \n    def gcd(self, a, b):\n        while b:\n            a, b = b, a % b\n        return a\n\n                \n\n\n\n        \n```
['Python']