# 600. Non-negative Integers without Consecutive Ones

Given a positive integer n, find the number of non-negative integers less than or equal to n, whose binary representations do NOT contain consecutive ones.

Example 1:

```Input: 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.
```

Note: 1 <= n <= 109

```class Solution(object):
def findIntegers(self, num):

def Find(n):

s = bin(n)[2:]
pre = '0'
flag = 1
for idx,d in enumerate(s):
if d == pre and pre == '1':
flag = 0
break
pre = d

if flag:
return s

ans = s[:idx]
nbit = 0
for i in range(idx,len(s)):
ans += str(nbit)
nbit ^=1

return ans

num = Find(num)
l = len(num)

cache = {0:1,1:2,2:3,3:5}

def sel(r):
if r in cache:
return cache[r]

cache[r] = sel(r-3)+sel(r-2)*2

return cache[r]

ans = 0

for idx, d in enumerate(num):
if d == '1':
r = l - idx - 1
ans += sel(r)

return ans+1```

Posted on Categories LeetCode