hardDynamic Programming 0 views
Non-negative Integers without Consecutive Ones
Given a positive integer n, return the number of the integers in the range [0, n] whose binary representations do not contain consecutive ones.
Given a positive integer n, return the number of the integers in the range [0, n] whose binary representations do not contain consecutive ones.
Example 1
Input: n = 5
Output: 5
Explanation: Here are the non-negative integers <= 5 with their corresponding binary representations: 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : 10^1 Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.
Example 2
Input: n = 1
Output: 2
Example 3
Input: n = 2
Output: 3
Constraints
- 1 <= n <= 10^9
Hints
No hints yet.
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.