Count number of binary strings without consecutive 1 â €™ s : Set 2 | 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 ; Calling the function ; Driver code
var memo = Array . from ( Array ( 32 ) , ( ) => Array ( 2 ) ) ; for ( var i = 0 ; i < 32 ; i ++ ) { for ( var j = 0 ; j < 2 ; j ++ ) { memo [ i ] [ j ] = new Array ( 2 ) . fill ( - 1 ) ; } } function dp ( pos , fl , pr , bin ) { if ( pos == bin . length ) return 1 ; if ( memo [ pos ] [ fl ] [ pr ] != - 1 ) return memo [ pos ] [ fl ] [ pr ] ; var val = 0 ; if ( bin [ pos ] == ' ' ) val = val + dp ( pos + 1 , fl , 0 , bin ) ; else if ( bin [ pos ] == ' ' ) 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 ] == ' ' ) { val += dp ( pos + 1 , fl , 1 , bin ) ; } } return memo [ pos ] [ fl ] [ pr ] = val ; } function findIntegers ( num ) { var bin = " " ; while ( num > 0 ) { if ( num % 2 ) bin += " " ; else bin += " " ; num = parseInt ( num / 2 ) ; } bin = bin . split ( ' ' ) . reverse ( ) . join ( ' ' ) return dp ( 0 , 0 , 0 , bin ) ; } var N = 12 ; document . write ( findIntegers ( N ) ) ;