Numbers of Length N having digits A and B and whose sum of digits contain only digits A and B | JavaScript implementation of the approach ; Function that returns true if the num contains a and b digits only ; Modular Exponentiation ; Function to return the modular inverse of x modulo MOD ; Function to return the required count of numbers ; Generating factorials of all numbers ; Generating inverse of factorials modulo MOD of all numbers ; Keeping a as largest number ; Iterate over all possible values of s and if it is a valid S then proceed further ; Check for invalid cases in the equation ; Find answer using combinatorics ; Add this result to final answer ; Driver Code
const MAX = ( 5 ) ; let MOD = ( 7 ) ; function check ( num , a , b ) { while ( num > 0 ) { var rem = num % 10 ; num = parseInt ( num / 10 ) ; if ( rem != a && rem != b ) return false ; } return true ; } function power ( x , y ) { var ans = 1 ; while ( y > 0 ) { if ( ( y & 1 ) > 0 ) ans = ( ans * x ) % MOD ; y >>= 1 ; x = ( x * x ) % MOD ; } return ans % MOD ; } function modInverse ( x ) { return power ( x , MOD - 2 ) ; } function countNumbers ( n , a , b ) { var fact = Array ( MAX ) . fill ( 0 ) ; var inv = Array ( MAX ) . fill ( 0 ) ; var ans = 0 ; fact [ 0 ] = 1 ; for ( var i = 1 ; i < MAX ; i ++ ) { fact [ i ] = ( 1 * fact [ i - 1 ] * i ) ; fact [ i ] %= MOD ; } inv [ MAX - 1 ] = modInverse ( fact [ MAX - 1 ] ) ; for ( i = MAX - 2 ; i >= 0 ; i -- ) { inv [ i ] = ( inv [ i + 1 ] * ( i + 1 ) ) ; inv [ i ] %= MOD ; } if ( a < b ) { var x = a ; a = b ; b = x ; } for ( s = n ; s <= 9 * n ; s ++ ) { if ( ! check ( s , a , b ) ) continue ; if ( s < n * b || ( s - n * b ) % ( a - b ) != 0 ) continue ; var numDig = parseInt ( ( ( s - n * b ) / ( a - b ) ) ) ; if ( numDig > n ) continue ; var curr = fact [ parseInt ( n ) ] ; curr = ( curr * inv [ numDig ] ) % MOD ; curr = ( curr * inv [ parseInt ( n - numDig ) ] ) % MOD ; ans = ( ans + curr ) % MOD ; } return ans ; } var n = 3 , a = 1 , b = 3 ; document . write ( countNumbers ( n , a , b ) ) ;