Group Theory/Cycle Decomposition Based Solution
Time Complexity = O(n)\n\nSome Math:\nLet S = {0,1,2,3,4...n-1}\nConsider a function f: S -> S\nsuch that f(i) = mapping i  according to the problem description
Time Complexity = O(n)\n\nSome Math:\nLet S = {0,1,2,3,4...n-1}\nConsider a function f: S -> S\nsuch that f(i) = mapping i  according to the problem description.\ni.e\nf(i) =  i/2 if (i is even)\nf(i) = ((i-1)/2 + n/2)  (if i is odd)\n\nf is a bijection on a S, hence f is a part of the permutation group of S (https://en.wikipedia.org/wiki/Permutation_group)\n\n\nThe question simply asks for o(f) (that is the smallest positive integer i, such that f^i = identity element)\nhttps://en.wikipedia.org/wiki/Order_(group_theory)#.\n\nConsider the cycle decomposition of f,\nthat f = f1f2....fk where each fi is a cycle permutation\n\nWe can easily argue that o(f)= lcm(o(f1), o(f2), ...o(fk))\n\nSince each fi is a cycle permutation o(fi) = length of the cycle they represent\n\nCode:\n```\nclass Solution {\n    private int gcd(int a, int b){\n        if (a > b) return gcd(b,a);\n        if (a == 0) return b;\n        return gcd(b%a, a);\n    }\n    private int lcm(int a, int b){\n        return (a*b)/gcd(a,b);\n    }\n    private int lcm(List<Integer> list){\n        int val = lcm(list.get(0),list.get(1));\n        for (int i = 2; i < list.size(); i++) val = lcm(val,list.get(i));\n        return val;\n    }\n    public int reinitializePermutation(int n) {\n        List<Integer> cycleSizes = new ArrayList();\n        boolean[] vis = new boolean[n];\n        for (int i = 0; i < n; i++){\n            if (vis[i]) continue; // i is already a part of some other cycle\n\t\t\t\n\t\t\t// Identify the cycle containing i\n            int j = i;\n            int cycleSize = 0;\n            while (!vis[j]){ // if we ever ecounter an element that is already visited then we have seen the entire cycle, so we can stop.\n                vis[j] = true;\n                cycleSize++;\n\t\t\t\t\n\t\t\t\t// applying f(j) to get next element\n                if (j%2 == 0) j = j/2;  \n                else j = ((j-1)/2) + n/2;\n                \n            }\n            cycleSizes.add(cycleSize); // remember the cycle sizes, since their sizes are their orders.\n        }\n        return lcm(cycleSizes); //compute the lcm of all the cycle sizes to get the order of our element.\n    }\n}\n```\n\n\n
['Math', 'Probability and Statistics']