dahiyakuldeep304's blog

Find the number of binary strings of length N with at least 3 consecutive 1s

By dahiyakuldeep304, history, 3 years ago, In English

we have an integer N, We have to find the number of all possible distinct binary strings of the length N, which have at least three consecutive 1s. So if n = 4, then the numbers will be 0111, 1110, 1111, so output will be 3.

Can anyone have any idea how to use dynamic programming here. It will be a great help. Thanks for advance.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Instead of counting directly, we will count the complement and subtract it from all possible strings, find the number of string where the length of the longest substring with all consecutive 1s is less than 3. Define

$$$dp[0][i] =$$$ $$$number$$$ $$$of$$$ $$$such$$$ $$$strings$$$ $$$with$$$ $$$length$$$ $$$i$$$ $$$that$$$ $$$ends$$$ $$$with$$$ $$$0$$$, $$$similarly$$$ $$$for$$$ $$$dp[1][i]$$$ $$$but$$$ $$$ending$$$ $$$with$$$ $$$1$$$ the transitions are as follows:

$$$dp[0][i] = \sum_{j=0}^{i-1} dp[1][j]$$$
$$$dp[1][i] = dp[0][i-1] + dp[0][i-2]$$$

the first transition is trying to add a block of 0s while the second tries to add a block of 1s, both can be done in $O(1)$ the final answer is

$$$2^{n}-dp[0][n]-dp[1][n]$$$
→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Let $$$f_n$$$ be the number of such ways. At $$$n^{th}$$$ position you can have $$$0/1$$$. If you have $$$0$$$, you solve for $$$f_{n-1}$$$. If we have $$$1$$$ we go to previous $$$(n-1)$$$ position. If it has a $$$0$$$, solve for $$$f_{n-2}$$$. If you have a $$$1$$$, go to $$$(n-2)$$$ position. If you find a $$$1$$$ here, we have got 3 consecutive ones, and so remaining $$$(n-3)$$$ can be any numbers. If we have a $$$0$$$ solve for $$$f_{n-3}$$$. Therefore the recurrence is:

$$$ f_n = f_{n-1} + f_{n-2} + f_{n-3} + 2^{n-3}$$$

$$$f_0 = 0, f_1 = 0, f_2 = 0$$$.

→ Reply