Given an array arr[] which contains the frequency of the digits (0-9), the task is to find the count of numbers possible using each digit its frequency times. That is, the final numbers generated should contain all of the digits their frequency times. Since, the count can be very large return the answer modulo 10^9+7. Prerequisites: Factorial of a number, Modular multiplicative inverse Examples:
Input : arr[] = {0, 1, 1, 0, 0, 0, 0, 0, 0, 0} Output : 2 Frequency of 1 and 2 is 1 and all the rest is 0. Therefore, 2 possible numbers are 12 and 21. Input : arr[] = {0, 5, 2, 0, 0, 0, 4, 0, 1, 1} Output : 1081080
Approach: The problem can be easily solved using Permutation and Combinations. The ith index of array arr[] gives the frequency of ith digit. The problem can be thought of as finding the total permutation of X objects where X0 objects are of one type, X1 objects are of another type and so on. Then the possible count of numbers is given by:
Total Count = X! / (X0! * X1! *…..* X9!)
where X = Sum of frequencies of all the digits and Xi = the frequency of ith digit. Below is the implementation of the above approach
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; #define ll long long #define MAXN 100000 #define MOD 1000000007 // Initialize an array to store factorial values ll fact[MAXN]; // Function to calculate and store X! values void factorial() { fact[0] = 1; for ( int i = 1; i < MAXN; i++) fact[i] = (fact[i - 1] * i) % MOD; } // Iterative Function to calculate (x^y)%p in O(log y) ll power(ll x, ll y, ll p) { ll res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } // Function that return modular // inverse of x under modulo p ll modInverse(ll x, ll p) { return power(x, p - 2, p); } // Function that returns the count of // different number possible by using // all the digits its frequency times ll countDifferentNumbers(ll arr[], ll P) { // Preprocess factorial values factorial(); // Initialize the result and sum // of all the frequencies ll res = 0, X = 0; // Calculate the sum of frequencies for ( int i = 0; i < 10; i++) X += arr[i]; // Putting res equal to x! res = fact[X]; // Multiplying res with modular // inverse of X0!, X1!, .., X9! for ( int i = 0; i < 10; i++) { if (arr[i] > 1) res = (res * modInverse(fact[arr[i]], P)) % P; } return res; } // Driver Code int main() { ll arr[] = { 1, 0, 2, 0, 0, 7, 4, 0, 0, 3 }; cout << countDifferentNumbers(arr, MOD); return 0; } |
Java
// Java program to implement // the above approach class GFG { static int MAXN = 100000 ; static int MOD = 1000000007 ; // Initialize an array to store factorial values static long fact[] = new long [MAXN]; // Function to calculate and store X! values static void factorial() { fact[ 0 ] = 1 ; for ( int i = 1 ; i < MAXN; i++) fact[i] = (fact[i - 1 ] * i) % MOD; } // Iterative Function to calculate (x^y)%p in O(log y) static long power( long x, long y, long p) { long res = 1 ; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0 ) { // If y is odd, multiply x with result if (y % 2 == 1 ) res = (res * x) % p; // y must be even now y = y >> 1 ; // y = y/2 x = (x * x) % p; } return res; } // Function that return modular // inverse of x under modulo p static long modInverse( long x, long p) { return power(x, p - 2 , p); } // Function that returns the count of // different number possible by using // along the digits its frequency times static long countDifferentNumbers( long arr[], long P) { // Preprocess factorial values factorial(); // Initialize the result and sum // of all the frequencies long res = 0 , X = 0 ; // Calculate the sum of frequencies for ( int i = 0 ; i < 10 ; i++) X += arr[i]; // Putting res equal to x! res = fact[( int )X]; // Multiplying res with modular // inverse of X0!, X1!, .., X9! for ( int i = 0 ; i < 10 ; i++) { if (arr[i] > 1 ) res = (res * modInverse(fact[( int )arr[i]], P)) % P; } return res; } // Driver Code public static void main(String[] args) { long arr[] = { 1 , 0 , 2 , 0 , 0 , 7 , 4 , 0 , 0 , 3 }; System.out.println(countDifferentNumbers(arr, MOD)); } } /* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 implementation of the above approach MAXN = 100000 MOD = 1000000007 # Initialize an array to store # factorial values fact = [ 0 ] * MAXN; # Function to calculate and store X! values def factorial() : fact[ 0 ] = 1 for i in range ( 1 , MAXN) : fact[i] = (fact[i - 1 ] * i) % MOD # Iterative Function to calculate # (x^y)%p in O(log y) def power(x, y, p) : res = 1 # Initialize result x = x % p # Update x if it is more than # or equal to p while (y > 0 ) : # If y is odd, multiply x with result if (y & 1 ) : res = (res * x) % p # y must be even now y = y >> 1 ; # y = y/2 x = (x * x) % p return res # Function that return modular # inverse of x under modulo p def modInverse(x, p) : return power(x, p - 2 , p) # Function that returns the count of # different number possible by using # all the digits its frequency times def countDifferentNumbers(arr, P) : # Preprocess factorial values factorial(); # Initialize the result and sum # of all the frequencies res = 0 ; X = 0 ; # Calculate the sum of frequencies for i in range ( 10 ) : X + = arr[i] # Putting res equal to x! res = fact[X] # Multiplying res with modular # inverse of X0!, X1!, .., X9! for i in range ( 10 ) : if (arr[i] > 1 ) : res = (res * modInverse(fact[arr[i]], P)) % P; return res; # Driver Code if __name__ = = "__main__" : arr = [ 1 , 0 , 2 , 0 , 0 , 7 , 4 , 0 , 0 , 3 ] print (countDifferentNumbers(arr, MOD)) # This code is contributed by Ryuga |
C#
// C# program to implement // the above approach using System; class GFG { static int MAXN = 100000; static int MOD = 1000000007; // Initialize an array to store factorial values static long []fact = new long [MAXN]; // Function to calculate and store X! values static void factorial() { fact[0] = 1; for ( int i = 1; i < MAXN; i++) fact[i] = (fact[i - 1] * i) % MOD; } // Iterative Function to calculate (x^y)%p in O(log y) static long power( long x, long y, long p) { long res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0) { // If y is odd, multiply x with result if (y % 2== 1) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } // Function that return modular // inverse of x under modulo p static long modInverse( long x, long p) { return power(x, p - 2, p); } // Function that returns the count of // different number possible by using // along the digits its frequency times static long countDifferentNumbers( long []arr, long P) { // Preprocess factorial values factorial(); // Initialize the result and sum // of all the frequencies long res = 0, X = 0; // Calculate the sum of frequencies for ( int i = 0; i < 10; i++) X += arr[i]; // Putting res equal to x! res = fact[( int )X]; // Multiplying res with modular // inverse of X0!, X1!, .., X9! for ( int i = 0; i < 10; i++) { if (arr[i] > 1) res = (res * modInverse(fact[( int )arr[i]], P)) % P; } return res; } // Driver Code public static void Main(String[] args) { long []arr = { 1, 0, 2, 0, 0, 7, 4, 0, 0, 3 }; Console.WriteLine(countDifferentNumbers(arr, MOD)); } } // This code has been contributed by 29AjayKumar |
Javascript
// JavaScript implementation of the above approach let MAXN = 100000n let MOD = 1000000007n // Initialize an array to store // factorial values let fact = new Array(MAXN).fill(0n); // Function to calculate and store X! values function factorial() { fact[0] = 1n for ( var i = 1n; i < MAXN; i++) fact[i] = (fact[i - 1n] * i) % MOD } // Iterative Function to calculate // (x^y)%p in O(log y) function power(x, y, p) { let res = 1n // Initialize result x = x % p // Update x if it is more than // or equal to p while (y > 0n) { // If y is odd, multiply x with result if (y & 1n) res = (res * x) % p // y must be even now y = y >> 1n; // y = y/2 x = (x * x) % p } return res } // Function that return modular // inverse of x under modulo p function modInverse(x, p) { return power(x, p - 2n, p) } // Function that returns the count of // different number possible by using // all the digits its frequency times function countDifferentNumbers(arr, P) { // Preprocess factorial values factorial(); // Initialize the result and sum // of all the frequencies let res = 0n; let X = 0n; // Calculate the sum of frequencies for ( var i = 0n; i < 10n; i++) X += arr[i] // Putting res equal to x! res = fact[X] // Multiplying res with modular // inverse of X0!, X1!, .., X9! for ( var i = 0n; i < 10n; i++) if (arr[i] > 1n) res = (res * modInverse(fact[arr[i]], P)) % P; return res; } // Driver Code let arr = [1n, 0n, 2n, 0n, 0n, 7n, 4n, 0n, 0n, 3n ] console.log(countDifferentNumbers(arr, MOD)) // This code is contributed by phasing17 |
245044800
Time Complexity: O(MAXN)
Auxiliary Space: O(MAXN)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!