Python solution with explanation


  • 1

    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.


Log in to reply
 

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