Подсчитайте различные числа, используя все цифры их частотного времени

Опубликовано: 14 Января, 2022

Учитывая массив arr [], который содержит частоту цифр (0–9), задача состоит в том, чтобы найти количество возможных чисел, используя каждую цифру ее частотное время. То есть, окончательные сгенерированные числа должны содержать все цифры их частотного времени. Поскольку счетчик может быть очень большим, верните ответ по модулю 10 ^ 9 + 7.

Предпосылки: Факториал числа, Модульное мультипликативное обратное
Примеры:

Ввод: arr [] = {0, 1, 1, 0, 0, 0, 0, 0, 0, 0}
Выход: 2
Частота 1 и 2 равна 1, а все остальные - 0. 
Следовательно, 2 возможных числа - 12 и 21.

Ввод: arr [] = {0, 5, 2, 0, 0, 0, 4, 0, 1, 1}.
Выход: 1081080

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход : проблема может быть легко решена с помощью перестановок и комбинаций. I- й индекс массива arr [] дает частоту i-й цифры. Проблему можно рассматривать как нахождение полной перестановки объектов X, где объекты X0 относятся к одному типу, объекты X1 относятся к другому типу и т. Д. Тогда возможное количество чисел определяется как:

Total Count = X! / (X0! * X1! *…..* X9!)

где X = сумма частот всех цифр и Xi = частота i-й цифры.

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 aint 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 aint 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 aint 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 aint 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
Output:
245044800

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ