Count strings with consecutive 1 's | Returns count of n length binary strings with consecutive 1 's ; Count binary strings without consecutive 1 's.  See the approach discussed on be  ( http:goo.gl/p8A3sW ) ; Subtract a [ n - 1 ] + b [ n - 1 ] from 2 ^ n ; Driver code
def countStrings ( n ) : NEW_LINE INDENT a = [ 0 ] * n NEW_LINE b = [ 0 ] * n NEW_LINE a [ 0 ] = b [ 0 ] = 1 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT a [ i ] = a [ i - 1 ] + b [ i - 1 ] NEW_LINE b [ i ] = a [ i - 1 ] NEW_LINE DEDENT return ( 1 << n ) - a [ n - 1 ] - b [ n - 1 ] NEW_LINE DEDENT print ( countStrings ( 5 ) ) NEW_LINE