Make delicious recipes!

Count strings without consecutive 1s

Problem: Given an integer N, count all the strings without consecutive 1s.
Assume that the strings are made up of only 0s and 1s

Solution: Let a be the number of strings without consecutive 1s and with last-character = 0

And let b be the number of strings without consecutive 1s but with last-character = 1

For a(k), we can append either 0 or 1 and the resulting strings would still be without consecutive 1s
For b(k), we can only append a 0 at the end.

Recursively, a(k+1) and b(k+1) can be written as:
a(k+1) = a(k) + b(k)
b(k+1) = a(k)

This is a perfect candidate for dynamic programming.
int countStringsWithout1s(int n)
    int a[n];
    int b[n];
    a[0] = 1;
    b[0] = 1;
    for (int i = 1; i < n; i++)
        a[i] = a[i-1] + b[i-1];
        b[i] = a[i-1];
    return a[n-1] + b[n-1];

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Email: (Your email is not shared with anybody)

Facebook comments:

Site Owner: Sachin Goyal