Scale Engineer

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

  1. Store the initial permutation [0, 1, ..., n-1] in a reference array, say initial.
  2. Create a working permutation array, perm, also initialized to [0, 1, ..., n-1].
  3. Initialize an operation counter, ops, to 0.
  4. Start a do-while loop or a while(true) loop.
  5. Inside the loop, increment ops.
  6. Create a new temporary array, arr, of size n.
  7. 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.
  8. Update perm to be equal to arr.
  9. The loop continues until the current perm becomes identical to the initial array.
  10. 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.

import java.util.Arrays; class Solution {    public int reinitializePermutation(int n) {        int[] initial = new int[n];        int[] perm = new int[n];        for (int i = 0; i < n; i++) {            initial[i] = i;            perm[i] = i;        }         int ops = 0;        // We need at least one operation, so a do-while loop is suitable.        do {            ops++;            int[] arr = new int[n];            for (int i = 0; i < n; i++) {                if (i % 2 == 0) {                    arr[i] = perm[i / 2];                } else {                    arr[i] = perm[n / 2 + (i - 1) / 2];                }            }            // Assign the new permutation to perm            perm = arr;        } while (!Arrays.equals(perm, initial));                return ops;    }}

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.

Solutions

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;      }    }  }}

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 →

Next problem