Sparse Bit Numbers Up To N
Problem
Call a non-negative integer sparse if its binary form has no two adjacent 1 bits (for example 5 = 101 is sparse, 6 = 110 is not).
Given n, return how many integers x with 0 ≤ x ≤ n are sparse.
Example 1
- Input:
- n = 5
- Output:
- 5
0, 1, 2 (10), 4 (100) and 5 (101) are sparse; 3 (11) is not.
Example 2
- Input:
- n = 8
- Output:
- 6
0, 1, 2, 4, 5, 8.
Constraints
- 0 ≤ n ≤ 10^9
Hint
Show the first hint
First count sparse bit strings of a fixed length k (leading zeros allowed): that is a small DP of its own.
Walkthrough
How to approach it
01Clarify before coding
- Is 0 counted? Yes, it has no 1 bits at all.
- Is n itself included? Yes, the range is inclusive.
- n up to 10^9: checking each x is 10^9 iterations, too slow.
02Brute force
Loop x from 0 to n and test (x & (x >> 1)) == 0.
Cost: O(n): a billion iterations at the limit.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.