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

 

Leave a Reply

Your email address will not be published. Required fields are marked *