Count number of binary strings without consecutive 1 â €™ s : Set 2 | C ++ program to count number of binary strings without consecutive 1 aTMs ; Table to store the solution of every sub problem ; Here , pos : keeps track of current position . f1 : is the flag to check if current number is less than N or not . pr : represents the previous digit ; Base case ; Check if this subproblem has already been solved ; Placing 0 at the current position as it does not violate the condition ; Here flag will be 1 for the next recursive call ; Placing 1 at this position only if the previously inserted number is 0 ; If the number is smaller than N ; If the digit at current position is 1 ; Storing the solution to this subproblem ; Function to find the number of integers less than or equal to N with no consecutive 1 aTMs in binary representation ; Convert N to binary form ; Loop to convert N from Decimal to binary ; Initialising the table with - 1. ; Calling the function ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int memo [ 32 ] [ 2 ] [ 2 ] ; int dp ( int pos , int fl , int pr , string & bin ) { if ( pos == bin . length ( ) ) return 1 ; if ( memo [ pos ] [ fl ] [ pr ] != -1 ) return memo [ pos ] [ fl ] [ pr ] ; int val = 0 ; if ( bin [ pos ] == '0' ) val = val + dp ( pos + 1 , fl , 0 , bin ) ; else if ( bin [ pos ] == '1' ) val = val + dp ( pos + 1 , 1 , 0 , bin ) ; if ( pr == 0 ) { if ( fl == 1 ) { val += dp ( pos + 1 , fl , 1 , bin ) ; } else if ( bin [ pos ] == '1' ) { val += dp ( pos + 1 , fl , 1 , bin ) ; } } return memo [ pos ] [ fl ] [ pr ] = val ; } int findIntegers ( int num ) { string bin ; while ( num > 0 ) { if ( num % 2 ) bin += "1" ; else bin += "0" ; num /= 2 ; } reverse ( bin . begin ( ) , bin . end ( ) ) ; memset ( memo , -1 , sizeof ( memo ) ) ; return dp ( 0 , 0 , 0 , bin ) ; } int main ( ) { int N = 12 ; cout << findIntegers ( N ) ; return 0 ; }