Given a range [x,y] find the count of numbers such that a number must have its count of set bits as a fibonacci number?
Eg: [15,17]
15 - 1111 - Count of bits is 4 - (4 is not a fibonacci number)
16 - 10000 - Count of bits is 1 - (1 is a fibonacci number)
17 - 10001 - Count of bits is 2 - (2 is a fibonacci number)
So answer is 2 (16,17)
Obviously we count the set bits and check whether its a fibonacci number using the condition whether (5x^2 +/- 4) is a perfect square..
NOTE: it's an interview question. The interviewer wasn't satisfied with the above approach.
Can we do any better?