anupomkar's blog

Number of steps required to sort the array using permutation array
By anupomkar, history, 2 years ago, In English

Given a permutation array P (1-based indexing), find the total number of steps required to sort the same array using the permutation array.

Constraints: n = arr.length 2<=n<=10^5

Example: Say P =[2,5,4,3,1]

Copy the array from P to arr arr = [2,5,4,3,1] step1 -> arr = [5,1,3,4,2] {Here the elements are arranged according to the permutation array, (i.e, permutation array P is considered here as index array to arrange elements) Here, 2nd element (5) comes 1st place because in P, 2 is at 1st position 5th element (1) comes 2nd place because in P, 5 is at 2nd position and so on...}

step2 -> arr = [1,2,4,3,5] step3 -> arr = [2,5,4,3,1] step4 -> arr = [5,1,4,3,2] step5 -> arr = [1,2,3,4,5]

Hence, the total number of steps required = 5

Expecting O(n) solution according to given constraints.

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

For a permutation $$$p$$$ with length $$$n$$$, consider a graph consisting of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$ , with a directed edge $$$u \to v$$$ iff $$$p_u=v$$$. Since every vertex has exactly one incoming edge and one outgoing edge, the graph must be made up of several cycles.

Then the problem can be rephrased as follows:

There are $$$n$$$ chesses on the graph. Initially, chess $$$i(1 \le i \le n)$$$ is on the vertex $$$p_i$$$. Every turn, all chesses will simultaneously move forward along one edge. After how many turns, every chess $$$i$$$ is exactly on vertex $$$i$$$ (for the first time)?

The answer to the problem is obviously the $$$\operatorname{lcm}$$$ of the lengths of the cycles in the graph minus one. ($$$\operatorname{lcm}$$$: the Lowest Common Multiple)

By calculating $$$\gcd$$$ (Greatest Common Divisor) in $$$O(\log{n})$$$ time, we can eaily get an $$$O(n\log{n})$$$ solution. However, the answer to the problem may be too large, so that probably we need to get the answer modulo by some number.

Instead of calculate $$$\operatorname{lcm}$$$ directly, we can precompute the prime factors of the lengths of the cycles, so that we can simply calculate $$$\max$$$ of the exponents of each prime factor. Finally, we just need to multiple the powers of the primes together, getting the answer modulo by some number. The total time complexity is $$$O(n)$$$, implementing properly.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I totally forgot to consider the LCM, I kept on talking the product of all cycle lengths. How did you realise that LCM has to be calculated? And are there any similar problems you've seen before, if yes please mention them here?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      For a cycle of length $$$k$$$, the chess on it will go back to the same place every $$$k$$$ turns. So if every chess has to go back, the number of turns must be the multiple of the length of every cycle, and the smallest one is naturally the $$$\operatorname{lcm}$$$ of the lengths.

      I believe this problem is classic, especially the trick to divide a permutation into several cycles. However, I can't list specific problems out.

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I think this problem is similar, https://codeforces.net/contest/1690/problem/F

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also, you can find the steps needed to achieve any arbitrary array (or report that it is impossible to achieve) with the Chinese Remainder Theorem.

    → Reply