Count number of binary strings without consecutive 1 â €™ s : Set 2 | Java 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 ; Utility reverse ; Driver code
class GFG { static int [ ] [ ] [ ] memo = new int [ 32 ] [ 2 ] [ 2 ] ; static 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 . charAt ( pos ) == '0' ) val = val + dp ( pos + 1 , fl , 0 , bin ) ; else if ( bin . charAt ( 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 . charAt ( pos ) == '1' ) { val += dp ( pos + 1 , fl , 1 , bin ) ; } } return memo [ pos ] [ fl ] [ pr ] = val ; } static int findIntegers ( int num ) { String bin = " " ; while ( num > 0 ) { if ( num % 2 == 1 ) bin += "1" ; else bin += "0" ; num /= 2 ; } bin = reverse ( bin ) ; for ( int i = 0 ; i < 32 ; i ++ ) { for ( int j = 0 ; j < 2 ; j ++ ) { for ( int l = 0 ; l < 2 ; l ++ ) memo [ i ] [ j ] [ l ] = - 1 ; } } return dp ( 0 , 0 , 0 , bin ) ; } static String reverse ( String input ) { char [ ] a = input . toCharArray ( ) ; int l , r = a . length - 1 ; for ( l = 0 ; l < r ; l ++ , r -- ) { char temp = a [ l ] ; a [ l ] = a [ r ] ; a [ r ] = temp ; } return String . valueOf ( a ) ; } public static void main ( String [ ] args ) { int N = 12 ; System . out . print ( findIntegers ( N ) ) ; } }