Fewest Moves to Switch Off the Row
A row of lamps shows the binary form of n: lamp 0 is the lowest bit, and a lamp is on where the bit is 1. One move does one of two things:
- flip lamp 0;
- flip lamp
ifor somei >= 1, which is allowed only when lampi - 1is on and every lamp belowi - 1is off.
Return the fewest moves that switch every lamp off.
Example 1
n 2
returns 3
The lamps go 10, 11, 01, 00: flip lamp 0, then lamp 1 (lamp 0 is on), then lamp 0 again.
Example 2
n 1
returns 1
One flip of lamp 0.
Example 3
n 0
returns 0
All the lamps are off already.
Constraints
0 <= n <= 10**9
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.