StaffDynamic Programming
Non-negative Integers without Consecutive Ones
Given a positive integer n, return the number of integers in the range [0, n] whose binary representations do not contain consecutive ones.
Example 1
Input
n = 5Output
5Among the integers from 0 through 5, only 3 has binary representation 11 with consecutive ones, so the other 5 integers satisfy the rule.
Example 2
Input
n = 1Output
2Both 0 and 1 have binary representations without consecutive ones.
Constraints
- 1 <= n <= 10^9