A polar research network operates n independent relay outposts, each broadcasting on its own frequency, and the network engineers want to consolidate them into a single master relay by running successive fusion cycles. In each fusion cycle, the engineers pair up as many of the current outposts as possible: every pair performs one fusion operation and becomes a single combined relay that carries into the next cycle, while at most one leftover outpost (whenever the count entering that cycle is odd) advances unfused because it has no partner. Fusion cycles repeat, each time roughly halving the outpost count in this manner, until exactly one master relay remains. Given the initial number of outposts, determine the total number of fusion operations performed over all cycles combined.
A single line containing one integer n, the initial number of outposts.
A single integer: the total number of fusion operations performed across every cycle until only one relay remains.
Example 1
Input
7
Expected
6
Explanation
Cycle 1: 7 outposts form 3 pairs (3 fusion operations) plus 1 leftover, leaving 3 fused + 1 leftover = 4 outposts. Cycle 2: 4 outposts form 2 pairs (2 operations), leaving 2 outposts. Cycle 3: those 2 form 1 pair (1 operation), leaving 1 master relay. Total operations = 3 + 2 + 1 = 6.
Example 2
Input
1
Expected
0
Explanation
There is already only one outpost, so it is already the master relay and zero fusion operations are ever performed.
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 →