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
memo = [ [ [ - 1 for i in range ( 2 ) ] for j in range ( 2 ) ] for k in range ( 32 ) ] NEW_LINE def dp ( pos , fl , pr , bin ) : NEW_LINE INDENT if ( pos == len ( bin ) ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT if ( memo [ pos ] [ fl ] [ pr ] != - 1 ) : NEW_LINE INDENT return memo [ pos ] [ fl ] [ pr ] ; NEW_LINE DEDENT val = 0 NEW_LINE if ( bin [ pos ] == '0' ) : NEW_LINE INDENT val = val + dp ( pos + 1 , fl , 0 , bin ) NEW_LINE DEDENT elif ( bin [ pos ] == '1' ) : NEW_LINE INDENT val = val + dp ( pos + 1 , 1 , 0 , bin ) NEW_LINE DEDENT if ( pr == 0 ) : NEW_LINE INDENT if ( fl == 1 ) : NEW_LINE INDENT val += dp ( pos + 1 , fl , 1 , bin ) NEW_LINE DEDENT elif ( bin [ pos ] == '1' ) : NEW_LINE INDENT val += dp ( pos + 1 , fl , 1 , bin ) NEW_LINE DEDENT DEDENT memo [ pos ] [ fl ] [ pr ] = val NEW_LINE return val NEW_LINE DEDENT def findIntegers ( num ) : NEW_LINE INDENT bin = " " NEW_LINE while ( num > 0 ) : NEW_LINE INDENT if ( num % 2 ) : NEW_LINE INDENT bin += "1" NEW_LINE DEDENT else : NEW_LINE INDENT bin += "0" NEW_LINE DEDENT num //= 2 NEW_LINE DEDENT bin = bin [ : : - 1 ] ; NEW_LINE return dp ( 0 , 0 , 0 , bin ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 12 NEW_LINE print ( findIntegers ( N ) ) NEW_LINE DEDENT