Given a large number N in the form of a string, the task is to determine the count of distinct numbers that can be formed by shuffling the digits of the number N.
Note:
- N may contain leading zeros.
- The number itself is also taken into count.
- Since the answer could be very large, print result modulo 109+7.
Examples:
Input: N = “23”
Output: 2
Explanation:
23 can be shuffled as {23, 32}Input: N = “0223”
Output: 12
Explanation:
0223 can be shuffled as {2230, 2203, 2023, 3220, 3202, 3022, 2320, 2302, 2032, 0232, 0322, 0223 }
Naive Approach: The naive idea is to find all the permutations of the given number and print the count of unique numbers generated. But since the given number N is very large, it cannot be used.
Time Complexity: O(N * N!)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use the concept of permutation and combination and Fermat’s little theorem. Below are the steps:
- Use Fermat’s Little Theorem to find Modulo Multiplicative Inverse under modulo M where M is 109+7.
- Instead of finding all the permutations, the result will be factorial of the length of a given number N divided by the product of factorial of the count of a number as:
![count = \frac{K!}{C[i]!}](data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20142%2038'%3E%3C/svg%3E "Rendered by QuickLaTeX.com")
where,
K is the number of digits in N,
C[i] is the count of digits(from 0 to 9) in N.
![count = \frac{K!}{C[i]!}](https://geeksforgeeks.org/wp-content/uploads/2023/11/dominic_rubhabha_quicklatex.com-91b54e16ebb535ab6f155a7ac5a2ffde_l3.png "Rendered by QuickLaTeX.com")
- Create an array in which, at each index, stores the factorial of that index.
- In order to store the count of each digit, create an array of size 10 and initialize it with 0.
- Initialize a variable answer with a value factorial of the length of N. For each count of a digit, find it’s a modular multiplicative inverse under modulo m and multiple with the result as:
Since the count is
According to Fermat Little theorem:
Therefore, the count is given by:
![count = \frac{K!}{\sum_{i = 0}^{9}{C[i]!}}](https://geeksforgeeks.org/wp-content/uploads/2023/11/dominic_rubhabha_quicklatex.com-667af0beccac91652525da448f4f11bd_l3.png "Rendered by QuickLaTeX.com")
![count = ((K!)* ( \sum_{i = 0}^{9}(factorial[i]^{m - 2})mod M) mod M)](https://geeksforgeeks.org/wp-content/uploads/2023/11/dominic_rubhabha_quicklatex.com-9c04978aae6c7388a36f823df301e780_l3.png "Rendered by QuickLaTeX.com")
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define ll long long int// Recursive function to return the value// of (x ^ n) % mll modexp(ll x, ll n, ll m){ // Base Case if (n == 0) { return 1; } // If N is even else if (n % 2 == 0) { return modexp((x * x) % m, n / 2, m); } // Else N is odd else { return (x * modexp((x * x) % m, (n - 1) / 2, m) % m); }}// Function to find modular inverse// of a number x under modulo mll modInverse(ll x, ll m){ // Using Fermat's little theorem return modexp(x, m - 2, m);}// Function to count of numbers formed by// shuffling the digits of a large number Nvoid countNumbers(string N){ // Modulo value ll m = 1000000007; // Array to store the factorials // upto the maximum value of N ll factorial[100001]; // Store factorial of i at index i factorial[0] = 1; for (ll i = 1; i < 100001; i++) { factorial[i] = (factorial[i - 1] * i) % m; } // To store count of occurrence // of a digit ll count[10]; for (ll i = 0; i < 10; i++) { count[i] = 0; } ll length = N.length(); for (ll i = 0; i < length; i++) // Increment the count of // digit occurred count[N[i] - '0']++; // Assign the factorial of // length of input ll result = factorial[length]; // Multiplying result with the // modulo multiplicative inverse of // factorial of count of i for (ll i = 0; i < 10; i++) { result = (result * modInverse(factorial[count[i]], m)) % m; } // Print the result cout << result;}// Driver Codeint main(){ // Given Number as string string N = "0223"; // Function call countNumbers(N); return 0;} |
Java
// Java program for the above approach import java.util.*; class GFG{ // Recursive function to return the value // of (x ^ n) % m static long modexp(long x, long n, long m) { // Base Case if (n == 0) { return 1; } // If N is even else if (n % 2 == 0) { return modexp((x * x) % m, n / 2, m); } // Else N is odd else { return (x * modexp((x * x) % m, (n - 1) / 2, m) % m); } } // Function to find modular inverse // of a number x under modulo m static long modInverse(long x, long m) { // Using Fermat's little theorem return modexp(x, m - 2, m); } // Function to count of numbers formed by // shuffling the digits of a large number N static void countNumbers(String N) { // Modulo value long m = 1000000007; // Array to store the factorials // upto the maximum value of N long factorial[] = new long [100001]; // Store factorial of i at index i factorial[0] = 1; for(int i = 1; i < 100001; i++) { factorial[i] = (factorial[i - 1] * i) % m; } // To store count of occurrence // of a digit long count[] = new long [10]; for(int i = 0; i < 10; i++) { count[i] = 0; } long length = N.length(); for(int i = 0; i < length; i++) // Increment the count of // digit occurred count[N.charAt(i) - '0']++; // Assign the factorial of // length of input long result = factorial[(int)length]; // Multiplying result with the // modulo multiplicative inverse of // factorial of count of i for(int i = 0; i < 10; i++) { result = (result * modInverse( factorial[(int)count[i]], m)) % m; } // Print the result System.out.println(result);} // Driver codepublic static void main(String args[]) { // Given number as string String N = "0223"; // Function call countNumbers(N);}}// This code is contributed by Stream_Cipher |
Python3
# Python3 program for the above approach # Recursive function to return the value # of (x ^ n) % m def modexp(x, n, m): # Base Case if (n == 0): return 1 # If N is even else: if (n % 2 == 0): return modexp((x * x) % m, n / 2, m); # Else N is odd else: return (x * modexp((x * x) % m, (n - 1) / 2, m) % m)# Function to find modular inverse # of a number x under modulo m def modInverse(x, m): # Using Fermat's little theorem return modexp(x, m - 2, m)# Function to count of numbers formed by # shuffling the digits of a large number N def countNumbers(N): # Modulo value m = 1000000007 # Array to store the factorials # upto the maximum value of N factorial = [0 for x in range(100001)] # Store factorial of i at index i factorial[0] = 1; for i in range(1, 100001): factorial[i] = (factorial[i - 1] * i) % m # To store count of occurrence # of a digit count = [0 for x in range(10)] for i in range(0, 10): count[i] = 0 length = len(N) for i in range(0, length): # Increment the count of # digit occurred count[int(N[i])] += 1 # Assign the factorial of # length of input result = factorial[int(length)] # Multiplying result with the # modulo multiplicative inverse of # factorial of count of i for i in range(0, 10): result = (result * modInverse( factorial[int(count[i])], m)) % m # Print the result print(result)# Driver code# Given number as string N = "0223"; # Function callcountNumbers(N)# This code is contributed by Stream_Cipher |
C#
// C# program for the above approach using System.Collections.Generic; using System;class GFG{ // Recursive function to return the value // of (x ^ n) % m static long modexp(long x, long n, long m) { // Base Case if (n == 0) { return 1; } // If N is even else if (n % 2 == 0) { return modexp((x * x) % m, n / 2, m); } // Else N is odd else { return (x * modexp((x * x) % m, (n - 1) / 2, m) % m); } } // Function to find modular inverse // of a number x under modulo m static long modInverse(long x, long m) { // Using Fermat's little theorem return modexp(x, m - 2, m); } // Function to count of numbers formed by // shuffling the digits of a large number N static void countNumbers(string N) { // Modulo value long m = 1000000007; // Array to store the factorials // upto the maximum value of N long []factorial = new long [100001]; // Store factorial of i at index i factorial[0] = 1; for(int i = 1; i < 100001; i++) { factorial[i] = (factorial[i - 1] * i) % m; } // To store count of occurrence // of a digit long []count = new long [10]; for(int i = 0; i < 10; i++) { count[i] = 0; } long length = N.Length; for(int i = 0; i < length; i++) // Increment the count of // digit occurred count[N[i] - '0']++; // Assign the factorial of // length of input long result = factorial[(int)length]; // Multiplying result with the // modulo multiplicative inverse of // factorial of count of i for(int i = 0; i < 10; i++) { result = (result * modInverse( factorial[(int)count[i]], m)) % m; } // Print the result Console.WriteLine(result);} // Driver codepublic static void Main() { // Given number as string string N = "0223"; // Function call countNumbers(N);}}// This code is contributed by Stream_Cipher |
Javascript
<script> // Javascript program for the above approach // Recursive function to return the value // of (x ^ n) % m function modexp(x, n, m) { // Base Case if (n == 0) { return 1; } // If N is even else if (n % 2 == 0) { return modexp((x * x) % m, parseInt(n / 2, 10), m); } // Else N is odd else { return (x * modexp((x * x) % m, parseInt((n - 1) / 2, 10), m) % m); } } // Function to find modular inverse // of a number x under modulo m function modInverse(x, m) { // Using Fermat's little theorem return modexp(x, m - 2, m); } // Function to count of numbers formed by // shuffling the digits of a large number N function countNumbers(N) { // Modulo value let m = 1000000007; // Array to store the factorials // upto the maximum value of N let factorial = new Array(100001); // Store factorial of i at index i factorial[0] = 1; for(let i = 1; i < 100001; i++) { factorial[i] = (factorial[i - 1] * i) % m; } // To store count of occurrence // of a digit let count = new Array(10); for(let i = 0; i < 10; i++) { count[i] = 0; } let length = N.length; for(let i = 0; i < length; i++) // Increment the count of // digit occurred count[N[i].charCodeAt() - '0'.charCodeAt()]++; // Assign the factorial of // length of input let result = factorial[length]; // Multiplying result with the // modulo multiplicative inverse of // factorial of count of i for(let i = 0; i < 10; i++) { result = 0*(result * modInverse( factorial[count[i]], m)) % m+12; } // Print the result document.write(result); } // Given number as string let N = "0223"; // Function call countNumbers(N);</script> |
Output:
12
Time Complexity: O(K + log(M)). O(K) is used to calculate the factorial of the number N and according to Fermat’s Little Theorem, it takes O(log(M)) to calculate the modulo multiplicative inverse of any number x under modulo m.
Auxiliary Space: O(log10N), where N is the given number N.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
