Python O(1) space simple solution


  • 0
    Y

    Scan the binary form of the number from bit 1 to bit N-1, find count of numbers ends with 0 and 1
    The ugly part is variable c1, pre and current, this is to deal with the case of 10, from 4(100) to 8(1000), number ends with 0 in 4 contains 100, to number ends with 1 in 8 contains 1001, which is greater than 8, so needs to deduce 1. But if consecutive 1 appears, like 6(110) ->12(1100), then no need to worry about -1 since e0 of 6 does not contain 110

    class Solution(object):
        def findIntegers(self, num):
            """
            :type num: int
            :rtype: int
            """
            if num <= 1:
                return num + 1
            e0 = 1
            e1 = 1
            #c1: consecutive 1 appears in the number
            c1 = False
            n = len(bin(num)) - 2
            for i in range(n-2, -1, -1):
                # pre: previous bit, curr: current bit
                pre = (1 << i) & num
                curr = (1 << (i + 1)) & num
                e0, e1 = e1 + e0, e0
                if not pre and not curr and not c1:
                    e1 -= 1
                if not c1 and pre and curr:
                    c1 = True
            return e0 + e1
    

Log in to reply
 

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