An old airfield's runway edge lighting rig is controlled by a single integer N: writing N in binary (no leading zeros) gives a left-to-right pattern of lit (1) and unlit (0) positions along the rig, where position 0 is the least significant bit. Maintenance wants to know how badly spaced the lit beacons are: among all pairs of lit positions that are consecutive when the lit positions are listed in increasing order (i.e. no other lit position lies between them), find the largest difference between their position indices. If the rig has fewer than two lit beacons, report 0.
A single line containing one integer N (1 <= N <= 10^9).
Print a single integer: the largest gap between two consecutive lit beacon positions, or 0 if N has fewer than two set bits.
Example 1
Input
22
Expected
2
Explanation
22 in binary is 10110, so bit position 0 is unset while positions 1, 2 and 4 are set (reading from the least significant bit). The consecutive lit pairs are (1,2), gap 1, and (2,4), gap 2. The largest gap is 2.
Example 2
Input
8
Expected
0
Explanation
8 in binary is 1000, so only bit position 3 is set. With fewer than two lit beacons there is no gap to measure, so the answer is 0.
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 →