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.