Python solution with explanation


  • 2

    x, y are used to calculate Fibonacci numbers.
    num & 1 and num & 2 will check if num ends with 11 in binary.

    Why can I use fibonacci numbers?
    a(n) = the number of valid integers less than 2^n
    a(5) = the number of valid integers less than 0b100000
    It equals to the number of valid integers in [0b0, 0b10000[ and in [0b10000, 0b11000[.
    The number of valid integers [0b0, 0b10000[, which is like '0b0XXXX', equals to a(4).
    The number of valid integers [0b10000, 0b11000[, which is like '0b101XX', equals to a(3).
    So a(5) = a(4) + a(3).
    This rule is the same for other values of n, and it is the same as Fibonacci numbers recurrence relation definition.

    def findIntegers(self, num):
            x, y = 1, 2
            res = 0
            num += 1
            while num:
                if num & 1 and num & 2:
                    res = 0
                res += x * (num & 1)
                num >>= 1
                x, y = y, x + y
            return res
    

    Shorter version:

    def findIntegers(self, num):
            res, x, y, num = 0, 1, 2, num + 1
            while num:  res, x, y, num = res if not num & 1 else x if num & 2 else res + x, y, x + y, num >> 1
            return res

  • 0
    L

    Could you explain your reasoning?


  • 0

    @livelearn
    x, y are used to calculate Fibonacci numbers.
    num & 1 and num & 2 will check if num ends with 11 in binary.


  • 0
    L

    Why can you use fibonacci numbers?


  • 0

    @livelearn
    a(n) = the number of valid integers less than 2^n
    a(5) = the number of valid integers less than 0b100000
    It equals to the number of valid integers in [0b0, 0b10000[ and in [0b10000, 0b11000[.
    The number of valid integers [0b0, 0b10000[, which is like '0b0XXXX', equals to a(4).
    The number of valid integers [0b10000, 0b11000[, which is like '0b101XX', equals to a(3).
    So a(5) = a(4) + a(3).
    This rule is the same for other values of n, and it is the same as Fibonacci numbers recurrence relation definition.


  • 0
    L

    @lee215
    For a(3) I think you meant to say valid integers [0b0,0b110]


Log in to reply
 

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