1806. Minimum Number of Operations to Reinitialize a Permutation - cocoder39/coco39_LC GitHub Wiki

1806. Minimum Number of Operations to Reinitialize a Permutation

If i % 2 == 0, then arr[i] = perm[i / 2].
If i % 2 == 1, then arr[i] = perm[n / 2 + (i - 1) / 2].

say j = i/2 => if i % 2 == 0, then arr[i] = perm[j] where i = 2*j
say j = n / 2 + (i - 1) / 2 => If i % 2 == 1, then arr[i] = perm[j] where i = 2*j - (n-1)

if i * 2 <= n-1, then arr_inverse[i] = perm[2 * i]
if i * 2 > n-1, then arr_inverse[i] = perm[2 * i - (n-1)]

So arr_inverse[i] = perm[(2 * i) % (n-1)]

class Solution:
    def reinitializePermutation(self, n: int) -> int:
        i = 1
        cnt = 0
        while cnt == 0 or i > 1:
            i = i * 2 % (n-1)
            cnt += 1
        return cnt

T = O(n) as i will iterate every element within range of n

seems like brute force option is also accepted.