1806. Minimum Number of Operations to Reinitialize a Permutation

MediumArrayMathSimulation
Leetcode Link

Problem Description

You are given an even integer n. Initially, you have a permutation perm of size n where each element of perm follows the rule perm[i] == i (with 0-based indexing). You will perform a series of operations on this permutation, and after each operation, a new array arr is created with the following rules:

  • If i is even, then the value of arr[i] becomes the value of perm[i / 2].
  • If i is odd, then the value of arr[i] becomes the value of perm[n / 2 + (i - 1) / 2].

After each operation, the arr becomes the new perm, and then you perform the same operation again on this new perm. The goal is to determine the minimum number of operations required to make the perm array return to its initial state where each element is perm[i] == i.

Intuition

To solve the problem efficiently, we need to observe the patterns that emerge when performing the operations on the permutation. The intuition comes from the fact that after each operation, some elements of the permutation will return to their original position before others. In particular, the element at index 1 has the potential to move through each position in the permutation since the operation exchanges elements in a certain cyclical pattern.

The solution involves tracking the new position of the element at index 1 after each operation. The cycle's length is determined by the number of steps it takes for index 1 to return to its original position (as other indices will follow a similar cycle pattern due to the same repetition of operations). The cycle length indicates the minimum non-zero number of operations required to return the entire permutation back to its initial state.

Hence, the approach is to simulate the process, tracking the index of the element at index 1 after each operation until it returns to its starting position. We increment a counter each time we perform an operation, and when the element at index 1 is back to position 1, we have the answer, which is the number of operations performed.

The steps for moving the element from index i during each operation, depending on whether i is even or odd, are directly applied in the code as conditional statements, with bitwise operations used to efficiently perform arithmetic calculations.

The bitwise operations used are:

  • i < n >> 1: In place of dividing n by 2 (n / 2), we use right shift operation which is faster.
  • i <<= 1: Instead of multiplying i by 2 (i * 2), we use a left shift, which effectively doubles the value of i.
  • i = (i - (n >> 1)) << 1 | 1: This is an optimized way of doing (2 * (i - n / 2)) + 1, again using bitwise shift and bitwise OR to set the last bit to 1 for odd positioning.

The solution capitalizes on these patterns and efficient bitwise operations to arrive at a quick and optimal solution.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Solution Approach

The code provided uses a simple while loop to simulate the operations on the permutation and identifies the number of operations needed to bring the array back to its initial state.

  • The variable ans is used to count the number of operations performed.
  • The variable i represents the current index of the element that started at index 1. The element at index 1 is special because, as per the problem statement, every other element's final position depends on this element's path back to index 1.

The while loop continues indefinitely until the element at index 1 returns to its initial position, which triggers the break condition i == 1.

Inside the while loop:

  • We increment ans by 1 for every iteration, representing an operation.
  • We then use a conditional statement to determine the new position of the element initially at index 1 after the operation.
    • If the current index i is less than half the size of the permutation (n >> 1), then the element goes to the position i * 2 (achieved by i <<= 1), which is an even-indexed position in the permutation.
    • If the current index i is greater or equal to half the size of the permutation, the element goes to the position (2 * (i - n / 2)) + 1 (achieved by i = (i - (n >> 1)) << 1 | 1), which is an odd-indexed position.
  • After each operation, the conditional checks if the element at index 1 has returned to its initial position. If i == 1, the loop terminates, and the variable ans is returned, which represents the minimum number of operations needed to reinitialize the permutation.

There are no additional data structures used, and the algorithm is not complex, as it relies on a simple simulation of the defined operation on the permutation. The pattern identified is that of a cycle wherein the element at index 1 eventually returns to its position after a set number of operations, which is the basis for calculating the answer. This simulation does not require modifying the array at each step and instead tracks the position of a single element, which keeps the space complexity to a constant.

This method is optimal because it avoids unnecessary computation by directly tracking the one element that determines the permutation's return to the initial state, taking advantage of the permuted array's specific structure of cycling through positions in a defined pattern.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Example Walkthrough

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

  1. After the first operation, according to the rules:

    • arr[0] = perm[0 / 2] = perm[0] = 0
    • arr[1] = perm[4 / 2 + (1 - 1) / 2] = perm[2 + 0] = perm[2] = 2
    • arr[2] = perm[2 / 2] = perm[1] = 1
    • arr[3] = perm[4 / 2 + (3 - 1) / 2] = perm[2 + 1] = perm[3] = 3

    The resulting arr after the first operation is [0, 2, 1, 3].

  2. We now set perm to the new arr, and repeat the operation. The element at index 1 is now at index 2.

  3. Applying the operation a second time:

    • arr[0] = perm[0 / 2] = perm[0] = 0
    • arr[1] = perm[4 / 2 + (1 - 1) / 2] = perm[2 + 0] = perm[2] = 1
    • arr[2] = perm[2 / 2] = perm[1] = 2
    • arr[3] = perm[4 / 2 + (3 - 1) / 2] = perm[2 + 1] = perm[3] = 3

    The resulting arr after the second operation is [0, 1, 2, 3], which is the initial state.

Therefore, the number of operations required for the permutation to return to its initial state is 2. This process can be generalised to find the cycle length for any even integer n.

Following the provided solution approach step-by-step:

  • We start with ans = 0 (number of operations performed) and i = 1 (element at index 1 in the initial permutation).
  • We execute the while loop with the break condition i == 1 not met since i starts at 1.
  • In the loop, we use bitwise operations to find the next index i based on whether it is currently in the first half or the second half of the permutation.
  • We continue this process and increment ans each time until the element initially at index 1 returns to index 1 again.
  • The loop terminates, and the value of ans tells us the minimum number of operations necessary.

Applying bitwise operations makes each calculation within the loop more efficient compared to using standard arithmetic operations.

Solution Implementation

1class Solution:
2    def reinitializePermutation(self, n: int) -> int:
3        # Initialize the number of operations performed to zero.
4        operation_count = 0
5        # Start with the index of the second element in the permutation.
6        index = 1
7      
8        # Use a loop to simulate the permutation process until the original order is restored.
9        while True:
10            # Increment the operation count each time a permutation is applied.
11            operation_count += 1
12            # If the current index is in the first half of the array (before n/2),
13            # apply the permutation formula for the first half.
14            if index < (n >> 1):
15                index <<= 1
16            # If the current index is in the second half of the array (from n/2 to n-1),
17            # apply the permutation formula for the second half.
18            else:
19                index = ((index - (n >> 1)) << 1) | 1
20          
21            # If the index is back to 1, the array has been reinitialized.
22            # Return the number of operations performed to reach this point.
23            if index == 1:
24                return operation_count
25
1class Solution {
2    public int reinitializePermutation(int n) {
3        int operationsCount = 0; // Initialize a counter to keep track of the number of operations
4        int index = 1; // Start with the element at index 1
5
6        // Loop indefinitely until we break out when the original position is restored
7        while (true) {
8            operationsCount++; // Increment the operation count
9
10            // If the current index is less than n/2,
11            // it corresponds to the first half of the permuted array
12            if (index < n / 2) {
13                index *= 2; // Double the current index
14            } else {
15                // Otherwise, it corresponds to the second half of the permuted array
16                // Perform the calculation of the new index according to the problem's formula
17                index = (index - n / 2) * 2 + 1;
18            }
19
20            // If the element has returned to its original position (index 1),
21            // break out of the loop
22            if (index == 1) {
23                break;
24            }
25        }
26
27        return operationsCount; // Return the number of operations needed
28    }
29}
30
1class Solution {
2public:
3    // Function to determine the minimum number of operations required
4    // to reinitialize a permutation to its original configuration.
5    int reinitializePermutation(int n) {
6        int numOperations = 0; // Initialize the count of operations to 0
7        for (int index = 1; ; ) { // Start with index set to 1
8            ++numOperations; // Increment the operation count
9          
10            // Check if the current index is in the first half of the array
11            if (index < (n / 2)) {
12                // If so, double the index
13                index *= 2;
14            } else {
15                // Else, calculate the new index based on the second half's rule
16                index = (index - (n / 2)) * 2 + 1;
17            }
18          
19            // If the index is back to 1, we've completed the reinitialization
20            if (index == 1) {
21                return numOperations; // Return the number of operations needed
22            }
23            // Loop continues until index is back to 1
24        }
25        // No need for a return statement here, as the loop will eventually return
26        // the count once the reinitialization condition is met.
27    }
28};
29
1// Function to determine the minimum number of operations required
2// to reinitialize a permutation to its original configuration.
3function reinitializePermutation(n: number): number {
4    let numOperations: number = 0;  // Initialize the count of operations to 0
5    for (let index: number = 1; ; ) { // Start with an index set to 1
6        numOperations++;  // Increment the operation count
7      
8        // Check if the current index is in the first half of the array.
9        if (index < (n / 2)) {
10            // If so, double the index.
11            index *= 2;
12        } else {
13            // Else, calculate the new index based on the second half's rule.
14            index = (index - (n / 2)) * 2 + 1;
15        }
16      
17        // If the index is back to 1, we've completed the reinitialization.
18        if (index === 1) {
19            return numOperations; // Return the number of operations needed.
20        }
21        // Loop continues until index is back to 1.
22    }
23    // No need for a return statement outside of the loop, as the loop will
24    // always return the count once the reinitialization condition is met.
25}
26
27// Example usage:
28// const minOperations = reinitializePermutation(4);
29
Not Sure What to Study? Take the 2-min Quiz：

Which data structure is used to implement priority queue?

Time and Space Complexity

The time complexity of the provided code is O(log n). This is because each iteration of the while loop either doubles the value of i (when i < n >> 1) or performs a sequence of operations that ultimately results in looping back towards 1 (when i >= n >> 1). The i value is halved in terms of its position in the original array. Since the value of i is halved in every step, it requires at most log2(n) steps to reach back to the starting position of i = 1.

The space complexity of the code is O(1). This is because the algorithm uses a fixed number of variables (ans, i, n) and does not allocate any additional space that scales with the input size n. Therefore, the amount of memory used remains constant regardless of the size of n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫