Loading...
Loading...
Loading...
For a group photo, n students stand in a line. Each student has different marks in the last test. The photographer wants them in increasing order of marks from left to right.
In one move, any two students can swap places. They do not have to stand next to each other. Print the fewest moves needed.
Example
Input
5 20 10 40 50 30
Output
3
20 and 10 swap with each other: 1 swap. 40 belongs where 50 stands, 50 where 30 stands, and 30 where 40 stands: a loop of 3 that needs 2 swaps. Total 3.
Try the problem first. Open one hint at a time.
Sort a copy of the marks. Now you know the final place of every student.
Follow the students: the student at place i must go to place p, the student at p must go to place q, and so on, until you return to i. This is a loop.
A loop of k students needs exactly k - 1 swaps. A student already in the right place is a loop of 1.
Mark every place you visit, so each loop is counted once.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor