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
iis even), then arr[i] = perm[i / 2]. - If i % 2 == 1 (i.e., index
iis 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
iis less thann / 2, then updateiwith the value ofi * 2. - Else, update
iwith 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.