Numbers of Length N having digits A and B and whose sum of digits contain only digits A and B | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 1e5 + 5 ; const int MOD = 1e9 + 7 ; #define ll  long long NEW_LINE int check ( int num , int a , int b ) { while ( num ) { int rem = num % 10 ; num /= 10 ; if ( rem != a && rem != b ) return 0 ; } return 1 ; } ll power ( ll x , ll y ) { ll ans = 1 ; while ( y ) { if ( y & 1 ) ans = ( ans * x ) % MOD ; y >>= 1 ; x = ( x * x ) % MOD ; } return ans % MOD ; } int modInverse ( int x ) { return power ( x , MOD - 2 ) ; } ll countNumbers ( int n , int a , int b ) { ll fact [ MAX ] , inv [ MAX ] ; ll ans = 0 ; fact [ 0 ] = 1 ; for ( int i = 1 ; i < MAX ; i ++ ) { fact [ i ] = ( 1LL * fact [ i - 1 ] * i ) ; fact [ i ] %= MOD ; } inv [ MAX - 1 ] = modInverse ( fact [ MAX - 1 ] ) ; for ( int i = MAX - 2 ; i >= 0 ; i -- ) { inv [ i ] = ( inv [ i + 1 ] * ( i + 1 ) ) ; inv [ i ] %= MOD ; } if ( a < b ) swap ( a , b ) ; for ( int s = n ; s <= 9 * n ; s ++ ) { if ( ! check ( s , a , b ) ) continue ; if ( s < n * b || ( s - n * b ) % ( a - b ) != 0 ) continue ; int numDig = ( s - n * b ) / ( a - b ) ; if ( numDig > n ) continue ; ll curr = fact [ n ] ; curr = ( curr * inv [ numDig ] ) % MOD ; curr = ( curr * inv [ n - numDig ] ) % MOD ; ans = ( ans + curr ) % MOD ; } return ans ; } int main ( ) { int n = 3 , a = 1 , b = 3 ; cout << countNumbers ( n , a , b ) ; return 0 ; }