Find the number of binary strings of length N with at least 3 consecutive 1 s | C ++ implementation of the approach ; Function that returns true if s contains three consecutive 1 's ; Function to return the count of required strings ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool check ( string & s ) { int n = s . length ( ) ; for ( int i = 2 ; i < n ; i ++ ) { if ( s [ i ] == '1' && s [ i - 1 ] == '1' && s [ i - 2 ] == '1' ) return 1 ; } return 0 ; } int countStr ( int i , string & s ) { if ( i < 0 ) { if ( check ( s ) ) return 1 ; return 0 ; } s [ i ] = '0' ; int ans = countStr ( i - 1 , s ) ; s [ i ] = '1' ; ans += countStr ( i - 1 , s ) ; s [ i ] = '0' ; return ans ; } int main ( ) { int N = 4 ; string s ( N , '0' ) ; cout << countStr ( N - 1 , s ) ; return 0 ; }