Count numbers formed by given two digit with sum having given digits | Java program to count the number of numbers formed by digits a and b exactly of a length N such that the sum of the digits of the number thus formed is of digits a and b . ; function to check if sum of digits is made of a and b ; sum of digits is 0 ; if any of digits in sum is other than a and b ; calculate the modInverse V / of a number in O ( log n ) ; q is quotient ; m is remainder now , process same as Euclid 's algo ; Update y and x ; Make x positive ; function to pregenerate factorials ; function to pre calculate the modInverse of factorials ; calculates the modInverse of the last factorial ; precalculates the modInverse of all factorials by formulae ; function that returns the value of nCi ; function that returns the count of numbers ; function call to pre - calculate the factorials and modInverse of factorials ; if a and b are same ; Driver Code
class GFG { static int mod = ( int ) ( 1e9 + 7 ) ; static int N = 1000005 ; static int fact [ ] = new int [ N ] , invfact [ ] = new int [ N ] ; static int check ( int x , int a , int b ) { if ( x == 0 ) { return 0 ; } while ( x > 0 ) { if ( x % 10 != a & x % 10 != b ) { return 0 ; } x /= 10 ; } return 1 ; } static int modInverse ( int a , int m ) { int m0 = m ; int y = 0 , x = 1 ; if ( m == 1 ) { return 0 ; } while ( a > 1 ) { int q = a / m ; int t = m ; m = a % m ; a = t ; t = y ; y = x - q * y ; x = t ; } if ( x < 0 ) { x += m0 ; } return x ; } static void pregenFact ( ) { fact [ 0 ] = fact [ 1 ] = 1 ; for ( int i = 1 ; i <= 1000000 ; ++ i ) { fact [ i ] = ( int ) ( ( long ) fact [ i - 1 ] * i % mod ) ; } } static void pregenInverse ( ) { invfact [ 0 ] = invfact [ 1 ] = 1 ; invfact [ 1000000 ] = modInverse ( fact [ 1000000 ] , mod ) ; for ( int i = 999999 ; i > 1 ; -- i ) { invfact [ i ] = ( int ) ( ( ( long ) invfact [ i + 1 ] * ( long ) ( i + 1 ) ) % mod ) ; } } static int comb ( int big , int small ) { return ( int ) ( ( long ) fact [ big ] * invfact [ small ] % mod * invfact [ big - small ] % mod ) ; } static int count ( int a , int b , int n ) { pregenFact ( ) ; pregenInverse ( ) ; if ( a == b ) { return ( check ( a * n , a , b ) ) ; } int ans = 0 ; for ( int i = 0 ; i <= n ; ++ i ) { if ( check ( i * a + ( n - i ) * b , a , b ) == 1 ) { ans = ( ans + comb ( n , i ) ) % mod ; } } return ans ; } public static void main ( String [ ] args ) { int a = 3 , b = 4 , n = 11028 ; System . out . println ( count ( a , b , n ) ) ; } }