Minimun Operations to Re Initialize Permutation

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.

Approach:

• Since each index comes back to its initial position after a specific interval of time so we can find the length of the cycle from each index and then compute the LCM of all the lengths that we obtain which is our required answer.
• But as each index comes back to its initial position through a certain cyclic path. So whenever we are visiting a particular index, we are visiting all such indexes that belong to the same cycle as in the case of a chosen index. Therefore, we need not to calculate the length of the cycle for each index separately.
• And in order to check that we are not visiting that index again, we will keep a visited array and whenever we visit that index we will mark that index as true.
• For example: consider N = 6 then we will obtain the following cycles:

=> 0 → 0
=> 1 → 2 → 4 → 3 → 1
=> 2 → 4 → 3 → 1 → 2 (This is redundant)
=> 3 → 1 → 2 → 4 → 3 (This is redundant)
=> 4 → 3 → 1 → 2 → 4 (This is redundant)
=> 5 → 5

• Now from the above example, it is clear that we have two different cycles but of different lengths, and the cycle with the longest length will help us to reinitialize the permutation.
• So our final answer will be the LCM of all the lengths of the distinct cycles that we can obtain. In the above example LCM(4 , 1) = 4.

Algorithm:

• Create a boolean array Visited to mark the indexes that are visited.
• Let curLCM be the LCM of all cycle lengths. Initialize it as 1.
• Now we will traverse over all the indexes from 0 to N-1 and for each Index that is not visited, we will perform the following steps:
  • Create a variable curIndex equal to that Index.
  • Also create a variable cycleLength initialized to 0 to find the length of cycle.
  • Now till the curIndex is not visited do following steps:
    • Update curIndex as visited.
    • Increment the count of cycleLength by one.
    • If curIndex is even update curIndex = curIndex/2 otherwise update curIndex = N/2 + (curIndex - 1)/2.
  • Set curLCM as the LCM of curLCM and cycleLength.
• Return the variable curLCM.

Approach:

• If we simulate some cases from the above approach, it can be seen that the length of the cycle to which index 1 belongs is always our answer.
• So we will simulate the positions of index 1 and find the number of operations it requires to come back again at its starting position.
• To simulate an Index we will perform the below operations on:
  • If Index is even, update Index = Index/2.
  • Otherwise update Index  = N/2 + (Index-1)/2.
• So just find out after how many steps value at index 1 will come back to its initial state.

Algorithm:

• Create two variables firstIndex initialized to 1 and Count initialized to 0 to count the total operations.
• Now we will run a loop till the value of firstIndex again becomes 1. Inside the loop we will perform the following steps:
  • If firstIndex is even, update firstIndex = firstIndex/2
  • Otherwise update firstIndex  = N/2 + (firstIndex-1)/2.
  • Increment the value of Count by one.
• As soon as the loop breaks, we will return Count which is the required answer.