Minimun Operations to Re Initialize Permutation

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
0 upvote
Asked in company
Amazon

Problem statement

In an interview of a company the interviewer asked a question to the student that you are given a permutation ‘permArray’ of length ‘N’ (N is always even) which is filled with values 0 to N-1 such that permArray[i] = i. The student has to perform operations on the ‘permArray’ which are given below.

In one operation, you will create a new array ‘ARR’, and for each i:

1) If i % 2 == 0, then ARR[i] = permArray[i / 2].
2) If i % 2 == 1, then ARR[i] = permArray[N / 2 + (i - 1) / 2].

You will then assign ARR to 'permArray'.

The student has to find the minimum number of non-zero operations to make the ‘permArray’ return to its original state. Assuming yourselves as the student, solve the question given by the interviewer.

Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer ‘T’, denoting the number of test cases. 

The first line of each test case contains an integer ‘N’, denoting the length of the permutation.
Output format : 
For each test case, print the minimum number of non-zero operations to make the given array back to its original state.

Output for each test case is printed on a separate line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
2 <= N <= 10^5
N%2 = 0

Where ‘T’ represents the number of test cases, ‘N’ represents the length of the permutation ‘permArray’.

Time Limit: 1 sec
Sample Input 1 :
2
2
4
Sample Output 1 :
1
2
Explanation 1 :
For the first test case, 
Initially, the ‘permArray’ will look like [0, 1]. Then we will create a new array ‘ARR’ which will look like [0,1] after performing the first operation and then assigning the values in ‘ARR’ to ‘permArray’. So ‘permArray’ will become [0, 1] which is the same as the original array. So the output will be 1.

For the second test case, 
Initially the ‘permArray’ will look like [0,1,2,3]. Then we will create a new array ‘ARR’ which will look like [0,2,1,3] after performing the first operation and then assigning the values in ‘ARR’ to ‘permArray’. So ‘permArray’ will become [0,2,1,3]. Then again we will create a new array ‘ARR’ which will look like [0,1, 2, 3] after performing the second operation and then assigning the values in ‘ARR’ to ‘permArray’. So ‘permArray’ will become [0,1,2,3] which is the same as the original array. So the output will be 2.
Sample Input 2 :
2
6
8
Sample Output 2 :
4
3
Hint

Try to simulate the process exactly as mentioned in the problem statement. 

Approaches (3)
Brute Force

 

Approach:

  • It is basically a simulation algorithm where we have to apply the brute force method to solve the problem.
  • In this approach, we will be modifying the permArray as per the given rules till the permArray becomes the original permArray back again.
  • To do so, we will start a while loop and in each iteration, we increase the count by 1 and we create the new array ARR by following the conditions stated in the problem.
  • As soon as the new array ARR becomes equal to the permArray we break out of the loop and return the count which is the required answer.
  • Note that our algorithm will not go into an infinite loop because every element in the permArray forms a unique cycle of its own and will always come back to its original position in at most N steps.
  • The operations used will never make the element acquire a position greater than N  so after a certain number of steps it would come back to its original position.

 

Algorithm:

  • Construct an array permArray of numbers from 0 to N-1.
  • Now create another array ARR of size N. 
  • Also, create a variable Count initialized with 0 to count the number of operations required to get back to the same permutation.
  • Now run a loop till we get the same permutation back. Inside the loop:
    • Run a loop from 0 to N-1 and fill the array ARR as per the rules given in the problem statement.
    • Now make array permArray equal to array ARR.
    • Increment the value of Count by 1.
    • Then check if each value in permArray is equal to its index i.e  permArray[index] = index.
    • If it returns true, break the loop and return the Count which is the required answer.
    • Otherwise, continue performing the same operations till we get the same initial permutation back.
Time Complexity

O(N^2), where ‘N’ is the length of the permutation.

 

Constructing the array permArray will take O(N) time. Each element in the permArray forms a cycle and comes back to its original state in atmost N steps which will take O(N) time, and in each iteration, we iterate through all the N elements of the permArray. Therefore, the overall time complexity will be O(N^2).

Space Complexity

O(N), where ‘N’ is the length of the permutation.

 

Since we are constructing two arrays permArray, and the ARR which takes O(N) space. So overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Minimun Operations to Re Initialize Permutation
Full screen
Console