#600
Non-negative Integers without Consecutive Ones
master · 1655 · lc hard +32 · verified · 41.8% accepted · 1,623 likes · top 22%
Description
Given a positive integer n, count all integers in the inclusive range [0, n] whose binary form contains no two adjacent 1 bits. Return that count.
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 : 101
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
Code
1
2
3