First let us start with counting the number of binary sequences having l**ength β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, 0**00**, 0**01**, 0**10**, 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