Count different numbers possible using all the digits their frequency times | Java program to implement the above approach ; Initialize an array to store factorial values ; Function to calculate and store X ! values ; Iterative Function to calculate ( x ^ y ) % p in O ( log y ) ; x = x % p ; Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now y = y >> 1 ; y = y / 2 ; Function that return modular inverse of x under modulo p ; Function that returns the count of different number possible by using along the digits its frequency times ; Preprocess factorial values ; Initialize the result and sum of aint the frequencies ; Calculate the sum of frequencies ; Putting res equal to x ! ; Multiplying res with modular inverse of X0 ! , X1 ! , . . , X9 ! ; Driver Code
class GFG { static int MAXN = 100000 ; static int MOD = 1000000007 ; static long fact [ ] = new long [ MAXN ] ; static void factorial ( ) { fact [ 0 ] = 1 ; for ( int i = 1 ; i < MAXN ; i ++ ) fact [ i ] = ( fact [ i - 1 ] * i ) % MOD ; } static long power ( long x , long y , long p ) { while ( y > 0 ) { if ( y % 2 == 1 ) res = ( res * x ) % p ; x = ( x * x ) % p ; } return res ; } static long modInverse ( long x , long p ) { return power ( x , p - 2 , p ) ; } static long countDifferentNumbers ( long arr [ ] , long P ) { factorial ( ) ; long res = 0 , X = 0 ; for ( int i = 0 ; i < 10 ; i ++ ) X += arr [ i ] ; res = fact [ ( int ) X ] ; for ( int i = 0 ; i < 10 ; i ++ ) { if ( arr [ i ] > 1 ) res = ( res * modInverse ( fact [ ( int ) arr [ i ] ] , P ) ) % P ; } return res ; } public static void main ( String [ ] args ) { long arr [ ] = { 1 , 0 , 2 , 0 , 0 , 7 , 4 , 0 , 0 , 3 } ; System . out . println ( countDifferentNumbers ( arr , MOD ) ) ; } }