We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The beautiful array is sorted array or reverse sorted array.
Suppose the array is [5 4 2 3 1]
Store it with its own index
[(5, 0), (4, 1), (2, 2), (3, 3), (1, 4)]
Sort the array with respect to data
[(1, 4), (2, 2), (3, 3), (4, 1), (5, 0)]
Extract shuffled indices
[4, 2, 3, 1, 0]
Now create cycles
(0, 4) and (1, 2, 3)
Go to 0th index of above array
Value at this position is 4 so go to 4th index
Value at new position is 0 which is same as start so stop
Similarly 1 -> 2 -> 3
1 is subtracted from each cycle length and then they are added
(2 - 1) + (3 - 1) = 3
This the swap for first case
Now the input array is reversed as [1 3 2 4 5] and the above steps are repeated
We get 2 values of swap counts. Print the minimum out of it.
Lily's Homework
You are viewing a single comment's thread. Return to all comments →
The beautiful array is sorted array or reverse sorted array.
Suppose the array is [5 4 2 3 1]
Store it with its own index [(5, 0), (4, 1), (2, 2), (3, 3), (1, 4)]
Sort the array with respect to data [(1, 4), (2, 2), (3, 3), (4, 1), (5, 0)]
Extract shuffled indices [4, 2, 3, 1, 0]
Now create cycles
(0, 4) and (1, 2, 3)
Go to 0th index of above array
Value at this position is 4 so go to 4th index
Value at new position is 0 which is same as start so stop
Similarly 1 -> 2 -> 3
1 is subtracted from each cycle length and then they are added (2 - 1) + (3 - 1) = 3
This the swap for first case
Now the input array is reversed as [1 3 2 4 5] and the above steps are repeated
We get 2 values of swap counts. Print the minimum out of it.