Non-negative Integers without Consecutive Ones

Intuition

Solution

class Solution:
    def findIntegers(self, num: int) -> int:
        num = bin(num)[2:]
        feb = [0, 1]
        while len(feb) <= len(num) + 1:
            feb.append(feb[-1] + feb[-2])

        ans = 0
        for i in range(len(num)):
            b = len(num) - i
            if b == 1:
                if num[i] == '1':
                    ans += 2
                else:
                    ans += 1
            elif num[i] == '1':
                if i < len(num) - 1 and num[i + 1] == '1':
                    ans += feb[b] + feb[b + 1]
                    break
                else:
                    ans += feb[b - 1] + feb[b]
        return ans