Count number of binary Strings

#1

Q : https://hack.codingblocks.com/contests/c/452/1272
Please provide some hint for this problem.

#2

Hey Shrey, in this problem you have to count all possible distinct binary strings of length N such that there are no consecutive 1’s.
For example:
N = 3
Then there can be 5 possible strings distinct binary strings of length 3 which are 000, 001, 010, 100, 101 .
Hint is try to find the recurrence relation in this problem and you can solve it using dynamic programming.
Another approach is you can observe a pattern exist for the no. of distinct strings of length N, so you can find that pattern also.

1 Like
#3

Hello Shrey !
This is a good application of Dynamic Programming .
For this problem , suppose for a string of particular length , you have the count of number of strings such that there are no consecutive ones and string ending with 1 as A , and similarly B as the count of such string ending with 0 . So basically your answer will be A+B .
Okay , so if you think about recurrence , it’s quite easy to guess . Suppose A[i] represents count of strings of length i ending with 0 , and B[i] represents such strings ending with 1 . Then , A[i]=A[i-1]+B[i-1] and B[i]=A[i-1] . And your answer for string of length n will be A[n]+B[n] .
I hope this will make some sense to you .

1 Like
#4

Beside DP there also a pattern which is forming try to find out that pattern.see the test cases properly u will see it

1 Like
#5

Yes I got that. Thank You