A research fleet is about to deploy a line of numbered buoys into the ocean. Each buoy is stamped with a non-negative integer ID, and every buoy's sonar array activates one pinger per 1 bit in the binary representation of its ID. The launch crew fires buoys with fewer active pingers first, since those settle faster; among buoys with the same number of active pingers, the buoy with the smaller ID launches first. Given the IDs of all buoys waiting on deck, in their current order, output the IDs rearranged into the exact order in which the buoys will launch.
n, the number of buoys.n space-separated integers, the buoy IDs, in their current deck order.n buoy IDs, space-separated, rearranged into launch order.Example 1
Input
4 5 3 7 1
Expected
1 3 5 7
Explanation
5 is 101 in binary (2 bits), 3 is 011 (2 bits), 7 is 111 (3 bits), 1 is 001 (1 bit). Buoy 1 has the fewest active pingers (1), so it launches first. Buoys 3 and 5 both have 2 active pingers, so the smaller ID, 3, launches next, then 5. Buoy 7 has the most active pingers (3) and launches last, giving 1 3 5 7.
Example 2
Input
4 0 8 8 2
Expected
0 2 8 8
Explanation
0 has zero active pingers (its binary representation has no 1 bits), so it launches first. 8 is 1000 and 2 is 10, each with exactly 1 active pinger; sorted by ID among that tie group, 2 comes before the two buoys labeled 8, giving 0 2 8 8.
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 →