## Algorithm

Problem Name: 600. 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.

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
```

Constraints:

• `1 <= n <= 109`

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findIntegers = function (num) {
const binary = num.toString(2)
const fibonacci = [1, 2]
for (let i = 2; i  <  binary.length; ++i) {
fibonacci.push(fibonacci[i - 2] + fibonacci[i - 1])
}
let answer = binary.indexOf('11') === -1 ? 1 : 0
for (let i = 0; i  <  binary.length; ++i) {
if (binary[i] === '1') {
answer += fibonacci[binary.length - 1 - i]
if (binary[i - 1] === '1') {
break
}
}
}
return answer
}
``````
Copy The Code &

Input

cmd
n = 5

Output

cmd
5

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findIntegers(self, num):
num, sub = bin(num)[2:], 0
zero, one = [1] * len(num), [1] * len(num)
for i in range(1, len(num)):
zero[i], one[i] = zero[i - 1] + one[i - 1], zero[i - 1]
for i in range(1, len(num)):
if num[i] == num[i - 1] == "1": break
if num[i] == num[i - 1] == "0": sub += one[-1 - i]
return zero[-1] + one[-1] - sub
``````
Copy The Code &

Input

cmd
n = 5

Output

cmd
5
Advertisements