Minimum number of operations to reinitialize a permutation

Array Math Simulation

72.7% acceptance

Feb 25, 2026

326

176

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn reinitialize_permutation(n: i32) -> i32 {
    let n = n as usize;
    let orig: Vec<usize> = (0..n).collect();
    let mut perm: Vec<usize> = orig.clone();
    let mut ops = 0;
    loop {
      let mut arr = vec![0usize; n];
      for i in 0..n {
        if i % 2 == 0 {
          arr[i] = perm[i / 2];
        } else {
          arr[i] = perm[n / 2 + (i - 1) / 2];
        }
      }
      perm = arr;
      ops += 1;
      if perm == orig {
        return ops;
      }
    }
  }
}