Description
Given a positive integer n, return the number of non-negative integers less than or equal to n that do not have consecutive 1s in their binary representation.
Examples
Input:
n = 5Output:
5Explanation:
0,1,2,4,5 are valid.
Input:
n = 1Output:
2Explanation:
Edge case with minimal input.
Input:
n = 10Output:
8Explanation:
Valid numbers are 0,1,2,4,5,8,9,10. Numbers 3(11), 6(110), 7(111) have consecutive 1s in binary and are excluded.
Constraints
- •
1 ≤ n ≤ 10⁹