Number of steps required to sort the array using permutation array

Revision en1, by anupomkar, 2022-07-30 19:25:53

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.

Tags permutations, sorting

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English anupomkar 2022-07-30 19:25:53 893 Initial revision (published)