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

Solution:

# brute force 解法
# O(n)
class Solution(object):
    def findIntegers(self, num):
        count = 0
        for i in range(0, num + 1):
            if self.isValid(i):
                count += 1
        return count

    def isValid(self, num):
        # get binary representation of num
        s = bin(num)[2:]    # bin(3) -> '0b11'; bin(3)[2:] -> '11'
        for i in range(0, len(s) - 1):
            if s[i] == '1' and s[i + 1] == '1':
                return False

        return True

# 最优解
class Solution(object):
    def findIntegers(self, num):
        """
        :type num: int
        :rtype: int
        """
        # num_bin[0] represent the higest effective bit
        # !!! num_bin is start with 1
        num_bin = str(bin(num))[2:]
        n = len(num_bin)

        # a[i] means number of binary string with length i
        # which do not contains any concecutive ones and which end in 0
        a = [0] * (n + 1)
        b = [0] * (n + 1)
        a[1] = b[1] = 1
        for i in range(2, n + 1):
            a[i] = a[i - 1] + b[i - 1]
            b[i] = a[i - 1]

        res = a[n] + b[n]

        # 举个1000的例子
        # 第一次遇到00，删除101* -> b[2]
        # 第二次遇到00， 删除1001 -> b[1]
        
        # 从高位到低位遍历
        for i in range(n - 1):
            # if num is 11**, then all permutations is less that it
            # we could break the for loop
            if num_bin[i] == num_bin[i + 1] == '1':
                break

            # if we met 01, according to the dp formula, the number of qualified integers
            # for first 0 should be 00 and 01, both of them are less than or equal to 01. The same for 10.

            # if we met 10, according to the dp formula, the number of qualified integers
            # for first 1 should be 10, It equal to 10

            # for 00, the number of qualified integers for first 0 should be 00 and 01,
            #  but 01 is greater than 00, we should subtract it.

            # for i == 1
            # if num is 1001, we need to delete 101*
            # because 101*  == b[2]
            # b[n - (i + 1)] -> b[4 - (1 + 1)]
            if num_bin[i] == num_bin[i + 1] == '0':
                # i + 1 is ith from the highest effective bit
                # (i + 1) start from 1
                res -= b[n - (i + 1)]

        return res


res = Solution().findIntegers(3)
print(res)  # 3

res = Solution().findIntegers(9)
print(res)  # 7  只有0b1010比9大