# Python solution with explanation

• `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``````

• Could you explain your reasoning?

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

• Why can you use fibonacci numbers?

• @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.

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

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