Count N | Stores the value of overlapping states ; Function to check whether a number have only digits X or Y or not ; Until sum is positive ; If any digit is not X or Y then return 0 ; Return 1 ; Function to find the count of numbers that are formed by digits X and Y and whose sum of digit also have digit X or Y ; Initialize dp array ; Base Case ; Check if sum of digits formed by only X or Y ; Return the already computed ; Place the digit X at the current position ; Place the digit Y at the current position ; Update current state result ; Driver Code ; Function Call
let dp = [ ] ; for ( let i = 0 ; i < 1005 ; i ++ ) { dp [ i ] = [ ] ; for ( let j = 0 ; j < 9005 ; j ++ ) { dp [ i ] [ j ] = 0 ; } } let mod = 1000000007 ; function check ( sum , x , y ) { while ( sum > 0 ) { let ln = sum % 10 ; if ( ln != x && ln != y ) { return 0 ; } sum = Math . floor ( sum / 10 ) ; } return 1 ; } function countNumbers ( n , x , y , sum ) { for ( let i = 0 ; i < 1005 ; i ++ ) { for ( let j = 0 ; j < 9005 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } if ( n == 0 ) { return check ( sum , x , y ) ; } if ( dp [ n ] [ sum ] != - 1 ) { return dp [ n ] [ sum ] % mod ; } let option1 = countNumbers ( n - 1 , x , y , sum + x ) % mod ; let option2 = countNumbers ( n - 1 , x , y , sum + y ) % mod ; return dp [ n ] [ sum ] = ( option1 + option2 ) % mod ; } let N = 3 , X = 1 , Y = 5 ; document . write ( countNumbers ( N , X , Y , 0 ) % mod ) ;