Q600: 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. 

Let’s say the number without consecutive ones is called “good number”. To count the number of “good number” with less than or equal to N bits is straight forward. In brief, we can maintain some states like the number of “good number” with at most j bits that ends with zero or one. With this setting up, we can have some recursion like:

• ngood_end_with_1[j] = ngood_end_with_0[j - 1]
• ngood_end_with_0[j] = ngood_end_with_1[j - 1] + ngood_end_with_0[j - 1]

OK, then the problem becomes how to count the number of “good number” <= the target (and it takes me forever to get it right, and this motivates me the write it down ..).

The initial idea is simple. Suppose the target is 10000, then we can simply count the “good number” with at most 4 bits (and add 1 at the end since we need to include 10000 as well). Then for a more complex number like 10100, then we can count 4-bit “good number"s and count “good number” like 100XX which means counting 2-bit “good number”. Still, we need extra 1 to count 10100. But what if we encounter 10110? Besides the 4-bit and 2-bit, we need to consider 1010X, essentially 1-bit. And no need to add extra 1 since we don’t want to count 10110.

So, we can scan from the leading “1” and count the n-bit “good number” and move to the next “1”. If the “1” is right after another “1”, we count the n-bit and then we can return since for number 11… then pattern 10X… has already included all “good number"s that is smaller than 11… . If we are not returning immediately, we need to add extra 1 (as discussed above).

Another tip to note, we need to initialize the number of 0-bit “good number” as 1 since it actually means the number of 0-bit “good number” with leading zero (in the form of 0X). So, it is 1 rather than 0.

Taking together, we have the Python submission.

class Solution:
    def findIntegers(self, num: int) -> int:
        if num <= 1:
            return num + 1
        num_str = "{0:b}".format(num)
        ngood_array = [ [ 0, 0 ] for i in range(len(num_str)) ]
        ngood_array[1][0] = 1
        ngood_array[1][1] = 1
        ngood_array[0][0] = 1
        for j in range(2, len(ngood_array)):
            ngood_array[j][0] = ngood_array[j - 1][0] + ngood_array[j - 1][1]
            ngood_array[j][1] = ngood_array[j - 1][0]
        res = sum(ngood_array[len(num_str) - 1])
        pos = 1
        prev = '1'
        while pos < len(num_str):
            if num_str[pos] == '1':
                res += sum(ngood_array[len(num_str) - pos - 1])
                if prev == '1':
                    return res
                
            prev = num_str[pos]
            pos += 1
        return res + 1