A release engineer maintains a queue of firmware build identifiers waiting to be published. Before a release train can ship, the queue must be listed in ascending order of each build's checksum, where the checksum of a build identifier is defined as the sum of its decimal digits. Builds that share the same checksum must then appear in ascending order of the build identifier itself. The engineer can reorder the queue only by repeatedly swapping the positions of any two builds currently in it, and wants to reach the required order using as few swaps as possible.
Given the queue in its current order, determine the minimum number of swaps needed to bring it into the required order.
Line 1: a single integer n, the number of firmware builds in the queue. Line 2: n space-separated integers a_1 ... a_n, the build identifiers in their current order.
Print a single integer: the minimum number of swaps required to reorder the queue so that builds appear in ascending order of checksum, with ties broken by ascending build identifier.
Example 1
Input
4 56 23 10 9
Expected
2
Explanation
The checksums are 56→11, 23→5, 10→1, 9→9, so the required order is [10, 23, 9, 56] (checksums 1, 5, 9, 11). Starting from [56, 23, 10, 9], swapping positions 1 and 3 gives [10, 23, 56, 9], then swapping positions 3 and 4 gives [10, 23, 9, 56], the required order, in 2 swaps. No single swap can fix all three misplaced builds at once, so 2 is minimum.
Example 2
Input
5 1 2 3 4 5
Expected
0
Explanation
Each identifier is a single digit, so its checksum equals its own value. The required order by ascending checksum is therefore [1, 2, 3, 4, 5], which is exactly the given order already, so 0 swaps are needed.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →