Hard

Quiz

#600 Non-negative Integers without Consecutive Ones

APPROACH

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

1 of 4

1:00

What is the optimal approach for this problem?