869. No Adjacent Ones
A telemetry radio rejects any packet counter whose binary form contains two neighbouring 1 bits, because adjacent set bits create interference on the line. Counters are non-negative integers written in binary without leading zeros, and the counter 0 counts as clean.
Given an integer n, return how many integers x with 0 <= x <= n have a binary representation that never has two consecutive 1 bits. For example, 10 is written 1010 and is clean, while 6 is written 110 and is not. Testing every value one at a time is far too slow when n reaches a billion, so work from the bits of n instead.
Example 1
- Input:
- n = 12
- Output:
- 8
- Explanation:
Counting 0 to 12 gives 13 numbers; 3 (11), 6 (110), 7 (111), 11 (1011) and 12 (1100) contain adjacent 1 bits, so 13 - 5 = 8 remain: 0, 1, 2, 4, 5, 8, 9, 10.
Example 2
- Input:
- n = 20
- Output:
- 12
- Explanation:
Up to 15 only 0, 1, 2, 4, 5, 8, 9, 10 are clean; among 16 to 20 the numbers 16, 17, 18 and 20 are clean while 19 (10011) is not, giving 8 + 4 = 12.
Constraints
- 0 ≤ n ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(log n)
- Space
- O(log n)