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:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal