Minimum Number of Operations to Reinitialize a Permutation

Med

#1652Time: O(k * n), where `k` is the number of operations required. In each step, we iterate through the array of size `n` to build the new permutation and another O(n) to compare. The number of operations `k` can be at most `n`. Thus, the worst-case time complexity is O(n^2).Space: O(n). We need to store the initial permutation, the current permutation, and the temporary array for the next permutation, each of size `n`.

Patterns

Math

Data structures

Array

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We start with the initial permutation perm = [0, 1, ..., n-1] and repeatedly apply the given transformation rule. We keep a count of the operations. After each operation, we check if the current permutation has returned to its initial state. The simulation stops when the permutation is reinitialized, and we return the operation count.

Algorithm

Store the initial permutation [0, 1, ..., n-1] in a reference array, say initial.
Create a working permutation array, perm, also initialized to [0, 1, ..., n-1].
Initialize an operation counter, ops, to 0.
Start a do-while loop or a while(true) loop.
Inside the loop, increment ops.
Create a new temporary array, arr, of size n.
Populate arr based on the current perm using the rules:
- arr[i] = perm[i / 2] for even i.
- arr[i] = perm[n / 2 + (i - 1) / 2] for odd i.
Update perm to be equal to arr.
The loop continues until the current perm becomes identical to the initial array.
After the loop terminates, return ops.

Walkthrough

The most straightforward way to solve the problem is to perform the simulation exactly as stated. We maintain the current state of the permutation, perm, and compare it against its initial state after each operation.

We begin by creating two arrays: initial to hold the starting permutation [0, 1, ..., n-1] for reference, and perm which will be transformed. We then enter a loop. In each iteration, we count it as one operation, create a new array arr based on the transformation rules applied to perm, and then update perm with the contents of arr. We then check if perm is equal to initial. Since we are looking for a non-zero number of operations, this process is guaranteed to execute at least once. The loop terminates when perm is reinitialized, and we return the total count of operations.

1import java.util.Arrays;2 3class Solution {4    public int reinitializePermutation(int n) {5        int[] initial = new int[n];6        int[] perm = new int[n];7        for (int i = 0; i < n; i++) {8            initial[i] = i;9            perm[i] = i;10        }11 12        int ops = 0;13        // We need at least one operation, so a do-while loop is suitable.14        do {15            ops++;16            int[] arr = new int[n];17            for (int i = 0; i < n; i++) {18                if (i % 2 == 0) {19                    arr[i] = perm[i / 2];20                } else {21                    arr[i] = perm[n / 2 + (i - 1) / 2];22                }23            }24            // Assign the new permutation to perm25            perm = arr;26        } while (!Arrays.equals(perm, initial));27        28        return ops;29    }30}

Complexity

Time

O(k * n), where `k` is the number of operations required. In each step, we iterate through the array of size `n` to build the new permutation and another O(n) to compare. The number of operations `k` can be at most `n`. Thus, the worst-case time complexity is O(n^2).

Space

O(n). We need to store the initial permutation, the current permutation, and the temporary array for the next permutation, each of size `n`.

Trade-offs

Pros

Simple to understand and implement as it directly models the problem statement.
Guaranteed to find the correct answer.

Cons

Inefficient for larger values of n due to repeated array creation and comparison.
Higher space complexity compared to more optimized approaches.

A more efficient approach comes from analyzing the movement of indices. We can observe that the indices 0 and n-1 are fixed points in this permutation. For any other index, its new position after one operation can be described by a mathematical formula. The number of operations to return the entire permutation to its initial state is the same as the number of operations for any single element (like element 1) to return to its original position. This is because the permutation operation is applied uniformly to all indices, and the order of the permutation is determined by the length of the cycle containing these indices.

Algorithm

Observe that indices 0 and n-1 are fixed points and do not change their values.
Analyze the movement of any other index, for example, index 1.
After one operation, the value at index 1 moves to a new position. Let's track this position.
Start with pos = 1 (the initial position of value 1). After the first operation, its new position will be 2 * 1 = 2.
Initialize an operation counter ops = 1 and the current position pos = 2.
Start a loop that continues as long as pos is not back to 1.
Inside the loop, update the position pos using the transformation rule:
- If pos < n / 2, pos = 2 * pos.
- If pos >= n / 2, pos = 2 * pos - n + 1.
Increment ops in each iteration.
When pos becomes 1, the loop terminates. Return ops.

Walkthrough

Instead of simulating the entire permutation, we can track the position of a single element. The elements at index 0 and n-1 always stay in place. Let's track the position of the element that starts at index 1.

The position of an element at index j moves to a new index i based on the inverse of the given rules. The new position i is 2*j if j < n/2 and 2*j - n + 1 if j >= n/2.

We can start with pos = 1. After one operation, the element at 1 moves to pos = 2*1 = 2. We can then repeatedly apply this transformation to the current position and count the operations until the position returns to 1. The number of operations required for this single element to complete its cycle is the answer for the entire permutation. This is because the permutation forms cycles, and the answer is the least common multiple (LCM) of the cycle lengths. It turns out that for this specific permutation, all relevant indices belong to cycles whose lengths divide the length of the cycle containing 1.

This reduces the problem from an O(n) operation per step to an O(1) operation per step.

1class Solution {2    public int reinitializePermutation(int n) {3        // For n=2, perm=[0,1] -> [0,1] in 1 op.4        if (n == 2) {5            return 1;6        }7 8        // We track the position of the element initially at index 1.9        // After 1 operation, the element at index 1 moves to index 2.10        int ops = 1;11        int pos = 2;12 13        // We continue until the element returns to index 1.14        while (pos != 1) {15            ops++;16            // Apply the position transformation rule17            if (pos < n / 2) {18                pos = 2 * pos;19            } else {20                pos = 2 * pos - (n - 1); // This is equivalent to 2*pos - n + 121            }22        }23 24        return ops;25    }26}

Complexity

Time

O(k), where `k` is the result. The loop runs exactly `k` times. Since `k` is the order of the permutation, `k` is at most `n`. Therefore, the time complexity is O(n).

Space

O(1). We only use a few variables to keep track of the current position and the operation count.

Trade-offs

Pros

Highly efficient with O(n) time complexity.
Constant space complexity, O(1), as it avoids creating and manipulating large arrays.

Cons

Requires a mathematical insight into the permutation's structure, which is less obvious than direct simulation.

Solutions

Solution

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

1class Solution:2    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

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem