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


  • 0
    Y
    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
    

Log in to reply
 

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