Skip to content

1806. Minimum Number of Operations to Reinitialize a Permutation

Description

You are given an even integer n​​​​​​. You initially have a permutation perm of size n​​ where perm[i] == i​ (0-indexed)​​​​.

In one operation, you will create a new array arr, and for each i:

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

You will then assign arr​​​​ to perm.

Return the minimum non-zero number of operations you need to perform on perm to return the permutation to its initial value.

 

Example 1:

Input: n = 2
Output: 1
Explanation: perm = [0,1] initially.
After the 1st operation, perm = [0,1]
So it takes only 1 operation.

Example 2:

Input: n = 4
Output: 2
Explanation: perm = [0,1,2,3] initially.
After the 1st operation, perm = [0,2,1,3]
After the 2nd operation, perm = [0,1,2,3]
So it takes only 2 operations.

Example 3:

Input: n = 6
Output: 4

 

Constraints:

  • 2 <= n <= 1000
  • n​​​​​​ is even.

Solutions

Solution 1: Find Pattern + Simulation

We observe the change pattern of the numbers and find that:

  1. The even-indexed numbers of the new array are the numbers in the first half of the original array in order;
  2. The odd-indexed numbers of the new array are the numbers in the second half of the original array in order.

That is, if the index \(i\) of a number in the original array is in the range [0, n >> 1), then the new index of this number is i << 1; otherwise, the new index is (i - (n >> 1)) << 1 | 1.

In addition, the path of number movement is the same in each round of operation. As long as a number (except for numbers \(0\) and \(n-1\)) returns to its original position, the entire sequence will be consistent with the previous one.

Therefore, we choose the number \(1\), whose initial index is also \(1\). Each time we move the number \(1\) to a new position, until the number \(1\) returns to its original position, we can get the minimum number of operations.

The time complexity is \(O(n)\), and the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def reinitializePermutation(self, n: int) -> int:
        ans, i = 0, 1
        while 1:
            ans += 1
            if i < n >> 1:
                i <<= 1
            else:
                i = (i - (n >> 1)) << 1 | 1
            if i == 1:
                return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int reinitializePermutation(int n) {
        int ans = 0;
        for (int i = 1;;) {
            ++ans;
            if (i < (n >> 1)) {
                i <<= 1;
            } else {
                i = (i - (n >> 1)) << 1 | 1;
            }
            if (i == 1) {
                return ans;
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int reinitializePermutation(int n) {
        int ans = 0;
        for (int i = 1;;) {
            ++ans;
            if (i < (n >> 1)) {
                i <<= 1;
            } else {
                i = (i - (n >> 1)) << 1 | 1;
            }
            if (i == 1) {
                return ans;
            }
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func reinitializePermutation(n int) (ans int) {
    for i := 1; ; {
        ans++
        if i < (n >> 1) {
            i <<= 1
        } else {
            i = (i-(n>>1))<<1 | 1
        }
        if i == 1 {
            return ans
        }
    }
}

Comments