Python, Straightforward with Explanation


  • 3

    Say X is the given number, and A = a list of that number in binary. For example, if X = 1234 = 0b10011010010, A = [1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0].

    We will perform a 'flag-dp': let dp[i][flag] = the answer for the number corresponding to A[i:], where flag = 1 if we have written a lower number than A[i] at some point in our writing process (and can now freely write higher numbers), else flag = 0.

    1234 has bitlength 11. With that example, we would try to write 11 binary digits (without writing consecutive 1s) from left to right, such that the number it represents is less than or equal to 1234.

    If our flag is down (flag = 0), then we cannot write a higher number than A[i]. If A[i] = 1, then we can write '10' or '0'. If A[i] = 0, we can only write '0'. We should check as we write a zero, to lower our flag if we wrote a lower number. This is what dp[.][A[i]] and dp[.][A[i+1]] do.

    If our flag is up, then we can freely write '10' or '0'.

    def findIntegers(self, X):
        A = map(int, bin(X)[2:])
        N = len(A)
        dp = [[0, 0] for _ in xrange(N+2)]
        dp[N] = dp[N+1] = [1, 1]
        
        for i in xrange(N-1, -1, -1):
            dp[i][0] = dp[i+1][A[i]] + A[i] * dp[i+2][i+1 < N and A[i+1]]
            dp[i][1] = dp[i+1][1] + dp[i+2][1]
    
        return dp[0][0]
    

Log in to reply
 

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