Conteo de números distintos formados al barajar los dígitos de un gran número N

Dado un gran número N en forma de string, la tarea es determinar la cantidad de números distintos que se pueden formar mezclando los dígitos del número N.

Nota:

N puede contener ceros a la izquierda.
El número en sí también se tiene en cuenta.
Dado que la respuesta podría ser muy grande, imprima el resultado módulo 10 ⁹ +7.

Ejemplos:

Entrada: N = “23”
Salida: 2
Explicación:
23 se puede barajar como {23, 32}

Entrada: N = “0223”
Salida: 12
Explicación:
0223 se puede barajar como {2230, 2203, 2023, 3220, 3202, 3022, 2320, 2302, 2032, 0232, 0322, 0223}

Enfoque ingenuo: la idea ingenua es encontrar todas las permutaciones del número dado e imprimir el recuento de números únicos generados. Pero como el número N dado es muy grande, no se puede usar.

Complejidad temporal: O(N * N!)
Espacio auxiliar: O(1)

Enfoque eficiente: Para optimizar el enfoque anterior, la idea es utilizar el concepto de permutación y combinación y el pequeño teorema de Fermat . A continuación se muestran los pasos:

Use el pequeño teorema de Fermat para encontrar el módulo inverso multiplicativo bajo el módulo M donde M es 10 ⁹ +7 .
En lugar de encontrar todas las permutaciones, el resultado será el factorial de la longitud de un número dado N dividido por el producto del factorial de la cuenta de un número como:

$count = \frac{K!}{C[i]!}$

donde,
K es el número de dígitos en N ,
C[i] es el conteo de dígitos (de 0 a 9 ) en N.

Cree una array en la que, en cada índice, almacene el factorial de ese índice.
Para almacenar el conteo de cada dígito , cree una array de tamaño 10 e inicialícela con 0.
Inicialice una respuesta variable con un valor factorial de la longitud de N . Para cada conteo de un dígito, encuentra que es un inverso multiplicativo modular bajo el módulo m y multiplícalo con el resultado como:

Dado que el conteo es
$count = \frac{K!}{\sum_{i = 0}^{9}{C[i]!}}$

Según el pequeño teorema de Fermat:
$x^{-1} mod M = x^{M - 2} mod M$

Por lo tanto, la cuenta está dada por:
$count = ((K!)* ( \sum_{i = 0}^{9}(factorial[i]^{m - 2})mod M) mod M)$

A continuación se muestra la implementación del enfoque anterior:

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) % m
ll 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 m
ll 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 N
void 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 Code
int 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 code
public 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 call
countNumbers(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 code
public 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>

Producción:

Complejidad temporal: O(K + log(M)). O(K) se utiliza para calcular el factorial del número N y, de acuerdo con el pequeño teorema de Fermat, se necesita O(log(M)) para calcular el módulo inverso multiplicativo de cualquier número x bajo módulo m.
Espacio Auxiliar: O(log ₁₀ N), donde N es el número dado N.

Publicación traducida automáticamente

Artículo escrito por ssaksham y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta