Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1’s.
Examples:
Input: N = 2 Output: 3 // The 3 strings are 00, 01, 10 Input: N = 3 Output: 5 // The 5 strings are 000, 001, 010, 100, 101
This problem can be solved using Dynamic Programming. Let a[i] be the number of binary strings of length i which do not contain any two consecutive 1’s and which end in 0. Similarly, let b[i] be the number of such strings which end in 1. We can append either 0 or 1 to a string ending in 0, but we can only append 0 to a string ending in 1. This yields the recurrence relation:
a[i] = a[i - 1] + b[i - 1] b[i] = a[i - 1]
The base cases of above recurrence are a[1] = b[1] = 1. The total number of strings of length i is just a[i] + b[i].
[ad type=”banner”]Following is the implementation of above solution. In the following implementation, indexes start from 0. So a[i] represents the number of binary strings for input length i+1. Similarly, b[i] represents binary strings for input length i+1.
[pastacode lang=”java” manual=”class%20Subset_sum%0A%7B%0A%20%20%20%20static%20%20int%20countStrings(int%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20a%5B%5D%20%3D%20new%20int%20%5Bn%5D%3B%0A%20%20%20%20%20%20%20%20int%20b%5B%5D%20%3D%20new%20int%20%5Bn%5D%3B%0A%20%20%20%20%20%20%20%20a%5B0%5D%20%3D%20b%5B0%5D%20%3D%201%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%201%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20a%5Bi%5D%20%3D%20a%5Bi-1%5D%20%2B%20b%5Bi-1%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20b%5Bi%5D%20%3D%20a%5Bi-1%5D%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20a%5Bn-1%5D%20%2B%20b%5Bn-1%5D%3B%0A%20%20%20%20%7D%0A%20%20%20%20%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0A%20%20%20%20public%20static%20void%20main%20(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20System.out.println(countStrings(3))%3B%0A%20%20%20%20%7D%0A%7D” message=”Java” highlight=”” provider=”manual”/]Output:
5
If we take a closer look at the pattern, we can observe that the count is actually (n+2)’th Fibonacci number for n >= 1. The Fibonacci Numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ….
n = 1, count = 2 = fib(3) n = 2, count = 3 = fib(4) n = 3, count = 5 = fib(5) n = 4, count = 8 = fib(6) n = 5, count = 13 = fib(7) ................[ad type=”banner”]