0

Question statement
Now we represent a natural number N by the maximum numbers that are less than or equal to N in Fibonacci sequence: N = b1*A1 + b2*A2 + …
Hence N can be represented as: bnbn-1…b1. For eg, 1 = 1f, 2 = 10f, etc.
On writing all N successively in Fibonacci system, we will obtain a sequence like this: 110… We call this “Fibonacci sequence till N in bit format”.
Input

T, the number of test cases, followed by T lines.
Each line containing the positive integer M, where 0<=M<=1018
Output

T lines of output, each line contain the positive integer, denoting the count of the numbers of times that bit 1 appears in first M bits of this sequence.
How to utilise fibonacci to solve this problem.

2
Contributors
1
Reply
3
Views
5 Years
Discussion Span
Last Post by Adak
0

Break it down:

1) you'll need to have a loop to generate the fibonacci sequences, and

2) you'll need to have logic to save the bit pattern of the number the user input, before your program enters the loop mentioned above.

Once you get that working, the rest is entirely trivial. Give that a try.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.