Permutation order
Let p be a permutation\n\n[ 0   1   2   3   4 ... ]\n[ 0  n/2  1 n/2+1 2 ... ]\n\n\nThen the operation can be expressed as a product of permutations: arr = p * 
Let p be a [permutation](https://en.wikipedia.org/wiki/Permutation)\n```\n[ 0   1   2   3   4 ... ]\n[ 0  n/2  1 n/2+1 2 ... ]\n```\n\nThen the operation can be expressed as a product of permutations: arr = p * perm (p acts first). After applying the operation k times we have arr = p^k * perm. Arrays arr and perm will be equal when p^k = id. Minimum k that satisfies this condition is the order ord(p) of the permutation p.\n\nLet us consider inverse of the p.\n```\n[ 0 1 2 ... n/2-1  n/2  n/2+1 ... n-1 ]\n[ 0 2 4 ...  n-2    1     3   ... n-1 ]\n```\nIt has the same order but is more simple.\n\nOrder of a permutation equals to the least common multiple of its cycles lengths. Numbers 0 and n-1 are cycles of length 1. Other numbers are mapped by the rule x -> 2 * x mod n-1. Length of the cycle that contains x equals to the smallest m such that (2^m-1) * x = 0 mod n-1. We calculate the length of cycle that contains 1. Length of other cycles will divide this value.\n\n```\nint reinitializePermutation(int n)\n{\n    if (n == 2) return 1;\n    int cycle = 1, x = 2;\n    while (x != 1) {\n        x = (x * 2) % (n - 1);\n        cycle++;\n    }\n    return cycle;\n}\n```\n\nTime complexity: O(n)\nSpace complexity: O(1)\n\n*Proof that length of the cycle that contains x divides length of the cycle that contains 1.* Length of the cycle that contains x equals to the smallest m_x such that (2^m_x-1) * x = 0 mod n-1. This condition can be rewritten as 2^m_x = 1 mod (n-1)/gcd(n-1,x). In other words m_x is an order of 2 modulo n-1/gcd(n-1,x). The value m_1 satisfies 2^m_1 = 1 mod n-1. From this equality we get 2^m_1 = 1 mod (n-1)/gcd(n-1,x). Standard argument for element order: if 2^m_1 = 1 then m_1 must be divisible by the order of 2 (m_x in our case). Otherwise we can divide m_1 by m_x (m_1 = q * m_x + r) and write 1 = 2^m_1 = 2^(q * m_x + r) = (2^m_x)^q * 2^r = 2^r modulo (n-1)/gcd(n-1,x) for some r > 0 smaller than m_x. And we get a contradiction to the fact that m_x is a smallest value.
[]