Question

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

Analysis

First let's get the binary representation of integer n bin_n [$$d_{L-1}$$,..., $$d_2$$, $$d_1$$, $$d_0$$] as a list with length = L.

Let's define:

ans(l) means the number of non-negative integers less than or equal to number [$$d_{l-1}$$,..., $$d_2$$, $$d_1$$, $$d_0$$] with No Consecutive ones.

total(l) means the number of l digits non-negative integers with No Consecutive ones (for example: l = 2, then total(2)=3, since we have 0b00 0b01 0b10)

ans(l)can be calculated by adding two parts:

ans_ends_zero(l) (d_l-1 = 0)and ans_ends_one(l)(d_l-1 = 1)

total(l) can also be calculated be add two parts:

total_ends_zero(l) (d_l-1 = 0) and total_ends_one(l) (d_l-1 = 1)

we have transfer equation:

if d_l-1 = 1:
    ans_ends_zero(l) = total(l-1)
    ans_ends_one(l) = ans_ends_zero(l-1)
else: # d_l-1 = 0
    ans_ends_zero(l) = ans_ends_zero(l-1) + ans_ends_one(l-1)
    ans_ends_one(l) = 0

total_ends_zero(l) = total_ends_zero(l-1) + total_ends_one(l-1)
total_ends_one(l) = total_ends_zero(l-1)

start status:

ans(l) = [ans_ends_zero(l), ans_ends_one(l)]
total(l) = [total_ends_zero(l), total_ends_one(l)]

ans(1) = [1, 1] if d_0 == 1 else [1, 0)
total(1) = [1, 1]

Solution

def find(a):
    ans = [1, 1] if a%2==1 else [1, 0]
    total = [1, 1]
    a /= 2
    while a > 0:
        digit = a%2
        if digit:
            ans[1] = ans[0]
            ans[0] = total[0]+total[1]
        else:
            ans[0] += ans[1]
            ans[1] = 0
        total[0], total[1] = total[0]+total[1], total[0]
        a /=2
    return ans[1]+ans[0]