First let us start with counting the number of binary sequences having length ‘n’ and no adjacent ones
We use the array “DP” to store the count corresponding to the length
First place in a binary sequence can be either 0 or 1
Now coming to the most interesting part,
On second place you can fill 0, irrespective of what you have filled before but if you want to fill up the 1 at this position it is necessary to fill 0 at the previous position
In simpler terms, it means that if you want to fill a position with ‘1’ it is necessary that its previous position is filled with ‘0’ and if you want to fill a position with ‘0’ its previous position can be filled by either ‘0’ or ‘1’
Read and try to understand the above line because it is the key to the solution
So for any length n, let us construct our binary sequence in the backward direction:
there are two possible things to fill either ‘0’ or ‘1’, if you fill ‘0’ you have to construct the ‘n-1’ length sequence in the same way, else if you fill ‘1’ it is need to be guaranteed that previous position is filled with ‘0’ so you have then to construct ‘n-2’ length sequence
So a general compute function can be given as:
def compute(n):
if n==0:
return 1
elif n==1:
return 2
else:
return compute(n-1)+compute(n-2)
This function looks very same as that of “Fibonacci” just the starting seed value are 1 and 2 instead of 0 and 1
In the above compute function, as you see that several sub-problems overlap and are computed repeatedly so this can be memoized and the value can be computed as:
def compute():
DP[0] = 1
DP[1] = 2
for i in range(2,n+1):
DP[i] = DP[i-1] + DP[i-2]
Now coming to the question, first thing is that if value of k is greater than DP[n] such a sequence cannot exist
Let us consider all the 2 length binary sequences having no adjacent ones, 00, 01, 10
Now considering all the 3 length binary sequences having no adjacent ones, 000, 001, 010, 100, 101
See the part in the bold in above line carefully, you see that if you fill ‘0’ then the sequence will be same as that for the n-1 length
Thus if the value of k is less than or equal to DP[n-1], you print the ‘0’ and start constructing the n-1 length sequence with the same value of k
But if the value of k is greater than DP[n-1], than you have to print the ‘10’ and start constructing the n-2 length sequence with value of k decreased by DP[n-1]
It is necessary that there are no two adjacent ones in the sequence, so if you fill ‘1’ at current position it is necessary to fill ‘0’ at next position thus we print ‘10’ in the above case
I recommend you first to solve this problem on your own, but if you are unable to solve, refer to my solution
Happy Coding