How to approach sep week-1’s question fibonacci system?
At first, the problem seems complex. And it is in fact complex in sense that you have to lots of stuff. But the individual things are not that complex. Lets break it up into small chunks.
1. Calculate f(n)
f(n) is a function which gives us number of all possible binary numbers of length n where we don’t have “11” as substring. For example, for n = 2, we have 00, 01 and 10. Note that in the question, all our terms start with 1. But not in this function. Here we can start with 0. No problem. Let’s call this type of binary number General Binary Number.
So how do we do that? Lets build some base case. f(1) = 2 (0,1) and f(2) = 3 (00,01,10). Next, for f(3), we can put a 0 or 1 at beginning. So f(3) = f(2) + f(1). That’s cause if we put 1, the next bit must be 0.
Therefore f(n) = f(n-1) + f(n-2).
2. Calculate mf(n)
mf(n) is a function which gives us number of all possible binary number of length n where we don’t have “11” as substring AND it begins with 1. This is the kind of binary number the question has asked us for. Let’s call this type of binary number Special Binary Number.
mf(1) = 1 (1) and mf(2) = 1 (10). For mf(3), we have to put 10 at beginning. For the third position, it can be any valid combination. This is where f(n) comes into play.
mf(n) = f(n-2)
3. Calculate len(n)
len(n) is a function which gives us the total length of the string if we concatenate all the Special binary numbers of length n.
len(1) = 1 (1). len(2) = 2 (10) len(3) = 6 (100101)… len(n) = n * mf(n)
4. Calculate one(n)
one(n) is a function that gives us number of 1’s in the concatenated General binary numbers of length n. That is, one(3) will give us number of 1’s in “000 001 010 100 101”.
one(1) = 1 , one(2) = 2 … one(n) = one(n-1) + f(n-2) + one(n-2). Think about how I derived this formula.
5. Calculate mone(n)
mone(n) is a function that gives us number of 1’s in the concatenated Special binary numbers of length n. That is mone(3) will give us number of 1’s in “100 101”
mone(1) = 1, mone(2) = 1 … mone(n) = f(n-2) + one(n-2). Think about this one two.
@@@@@@@@@@@@@@@@@@@Pre-calculation Complete@@@@@@@@@@@@@@@@@@@@@@
Okey, now we are going to use this functions to get our result.
Lets write the concatenated Special Binary Numbers to see how things are going to work.
1
10
100
101
1000
1001
10000
10001
10010
10100
10101
Suppose N is 20. Here is how we will use the functions.
6. Traverse len(n)
We will traverse len() from 1. If len(i) <= N, then means, all the Special binary number of length n, can be removed from N and we can add mone(i) to our result.
len(1) = 1. N = N - 1 = 19. res += 1.
len(2) = 2. N = 19 - 2 = 17. res += 1.
len(3) = 6. N = 17 - 6 = 11. res += 3.
len(4) = 12. 12 > N. Therefore we stop here.
Our current result is 5. And that is indeed correct. For the first 9 bits, we have 5 one. “110100101”
So, we have N = 11, and we stopped at len(4). Let StopLen be 4. So we now know that the remaining prefix comes from the concatenation of special binary numbers of length 4 (StopLen). From the first 11 bits of “100010011010”. How do we get them?
7. Find Complete Numbers
We have “100010011010”. From the first 11 bits, how many complete binary numbers we have?
“1000 1001” and “101”. We have two complete binary numbers and a partial number of length 3. We can calculate them easily.
X = N / StopLen
R = N % StopLen
8. Calculate One in Complete Binary Numbers
How many one’s are there in the first X complete numbers? Well, X complete numbers have “10” at the beginning. So we can easily add X to result, and then find how many one is there in the first X elements of General binary number of length StopLen - 2. We will use recursion to find the answer. reucr ( StopLen - 2, X ).
void recurs ( int len, int Need ) // Something like this
At each state, we can put 0 at beginning. If we do that, there is f(len-1) possible binary numbers. If f(len-1)< Need, we can just add one(len-1) to result and call subtract f(len-1) from Need. Then try putting 1 at front. If f(len-1) >= Need, we HAVE to put 0 here and move forward, recur (len-1,need).
If we put 1, we have to put 0 after it. There is Need number of elements left. So for putting 1 here, we have to add Need to result. Then recur ( len - 2, Need ).
I leave the base cases for you. I am sure you can figure it out.
9. Calculate 1 in Partial Binary Number
The last step, how many 1 are there in the partial binary number that’s left at the end? Using somewhat the same logic as the recursion function above, simply build the number. The add all the one present in the first R bits.
I am leaving this one out too. This thing is getting too big!
@@@@@@@@@@@@@@@@@@@End@@@@@@@@@@@@@@@@@@@@@@@@@
This thing is so big that I don’t even feel like revising. If you find any error, let me know. I have explained all the major parts needed to solve this thing, the rest can figured out easily. Keep thinking.
7 Likes
thanks…
very well expalined…
@phanton002: If this answers your question, then you should cote up the answer and accept it as well.
k…:)
Wow. My first Accepted answer :D. Thanks guys