Leetcode 1806. Minimum Number of Operations to Reinitialize a Permutation Solution

Problem Explanation

The problem is asking us to perform a series of operations on an initially sorted array of an even number of elements, and return the minimum required operations to bring the array back to its initial sorted state.

We are given an even integer n, and a permutation perm of size n such that perm[i] == i. In each operation, we create a new array arr and assign values to arr as follows:

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

After each operation, we update the initial array perm with the values of the new array arr. The goal is to find the minimum non-zero number of times we have to perform this operation to return perm back to its initial sorted state.

Solution Approach

To solve this problem, we can use a simple loop with modular arithmetic. We start with an index i = 1 and iterate through the loop until i becomes 1 again. In each iteration of the loop, we update i according to some condition checks, which are as follows:

  • If i is less than n / 2, then update i with the value of i * 2.
  • Else, update i with the value of (i - n / 2) * 2 + 1.

We also increment the answer, which is the minimum number of operations required, in each iteration of the loop. Finally, we return the answer as the final result.

Example

Let's walk through the solution approach with an example input of n = 4. The initial permutation is perm = [0, 1, 2, 3].

  • In the first operation:
    • Update i (i = 1 * 2 = 2) because i = 1 < n / 2 = 2, and increment the answer (ans = 1).
    • After the first operation, perm becomes [0, 2, 1, 3].
  • In the second operation:
    • Update i (i = (2 - n / 2) * 2 + 1 = 1) because i = 2 >= n / 2 = 2, and increment the answer (ans = 2).
    • After the second operation, perm becomes [0, 1, 2, 3].

Since we've returned to the initial sorted state, we can stop the operation and return the answer, which is 2 in this case.

Python Solution

1class Solution:
2    def reinitializePermutation(self, n: int) -> int:
3        ans = 0
4        i = 1
5
6        while True:
7            if i < n // 2:
8                i = i * 2
9            else:
10                i = (i - n // 2) * 2 + 1
11            ans += 1
12            
13            if i == 1:
14                break
15
16        return ans

Java Solution

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

JavaScript Solution

1class Solution {
2  reinitializePermutation(n) {
3    let ans = 0;
4    let i = 1;
5
6    do {
7      if (i < n / 2)
8        i = i * 2;
9      else
10        i = (i - n / 2) * 2 + 1;
11      ans++;
12    } while (i != 1);
13
14    return ans;
15  }
16}

C++ Solution

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

C# Solution

1public class Solution {
2    public int ReinitializePermutation(int n) {
3        int ans = 0;
4        int i = 1;
5
6        do {
7            if (i < n / 2)
8                i = i * 2;
9            else
10                i = (i - n / 2) * 2 + 1;
11            ans++;
12        } while (i != 1);
13
14        return ans;
15    }
16}

Time and Space Complexities

The time complexity for all solutions above is O(log N) because we update the index i with factors of two until it goes back to 1, and the maximum number of times we can divide an even integer by 2 is proportional to its logarithm base 2. The space complexity of each solution is O(1) since we only use a constant amount of extra space to store variables other than the input.

To summarize, we demonstrated the solution using a loop with modular arithmetic to find the minimum number of times required to perform the given operation and return the initial permutation to its sorted state. We also provided implementations in multiple programming languages, and examined the time and space complexity of the solution.