O(1) time/space complexity in python, explanation included.

• ``````class Solution:
def findIntegers(self, num):
"""
:type num: int
:rtype: int
"""

i = 0               # the index of next bit to process, or the number of bits we have processed
n_end_with_0 = 1    # number of values that use i bit(s), ending with 0 and have no consecutive 1s
n_end_with_1 = 0    # number of values that use i bit(s), ending with 1 and have no consecutive 1s
n = 0               # the number of values that has no consecutive 1s.
last_bit_mask = 0x1

num += 1                # Since the our algorithm only looks at numbers
# in [0, num), we add the original num by 1.
# You shall see this after reading the comments
# in the loop body
while num > 0:
# Notation:
# - x: the bit being processed in this iteration
# - p: bits before the bit x, named after prefix.
# - We call a number that has no consecutive 1's a DESIRED number
#
# In each iteration, we compute the number of values in [ p00..0, px0..0 )
# - if p is a desired number or x is 0, then 0
# - else the number is equal to the count of desired numbers in [000...0, 100...0),
#   or [000...0, 011...1], this problem can be solver by DP.

num >>= 1           # note now p == num
# (x & (x << 1)): quick way to test if x has consecutive 1s, be careful with overflow.
if (num & (num << 1)) == 0 and (num & last_bit_mask) == 1:
n += n_end_with_1 + n_end_with_0

i += 1
n_end_with_0, n_end_with_1 = n_end_with_1 + n_end_with_0, n_end_with_0

return n
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.