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
O(1) time/space complexity in python, explanation included.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.