Recuento de números de N dígitos con al menos un dígito repetido

Dado un entero positivo N , la tarea es encontrar el número de números de N dígitos tales que al menos un dígito en el número haya ocurrido más de una vez. 

Ejemplos:

Entrada: N = 2
Salida: 9
Explicación:
Todos los números de 2 dígitos de los que al menos 1 dígito aparece más de una vez son {11, 22, 33, 44, 55, 66, 77, 88, 99}. Por lo tanto, el conteo total es 9.

Entrada: N = 5
Salida: 62784

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los números posibles de N dígitos y contar esos números que tienen al menos un dígito que aparece más de una vez. Después de verificar todos los números, imprima el valor del conteo como el conteo total de números resultante.

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

Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de la programación dinámica porque el problema anterior tiene subproblemas superpuestos y una subestructura óptima . Los subproblemas se pueden almacenar en la memorización de la tabla dp [][][] donde dp[dígito][máscara][repetida] almacena la respuesta desde la posición del dígito th hasta el final, donde la máscara almacena todos los dígitos incluidos en el número hasta ahora y repetido indica si algún dígito se ha producido más de una vez. Siga los pasos a continuación para resolver el problema:

  • Inicialice una array multidimensional global dp[50][1024][2] con todos los valores como -1 que almacena el resultado de cada llamada recursiva.
  • Defina una función recursiva , digamos contarDeNúmeros(dígito, máscara, repetido, N) realizando los siguientes pasos.
    • Si el valor de un dígito es igual a (N + 1) , se devuelve 1 como un número válido de N dígitos si repetido es igual a verdadero . De lo contrario, devuelve 0 .
    • Si repeat es igual a true , devuelve pow(10, N – digit + 1) .
    • Si el resultado del estado dp[digit][mask][repeated] ya se calculó, devuelva este valor dp[digit][mask][repeated] .
    • Si el dígito actual es 1 , entonces se puede colocar cualquier dígito de [1, 9] y si N = 1 , entonces también se puede colocar 0 .
    • Iterar sobre el rango [N == 1 ? 0 : 1, 9] usando la variable i y realice los siguientes pasos:
    • De lo contrario, itere sobre el rango [0, 9] usando la variable i y realice los siguientes pasos:
    • Devuelve la suma de todas las ubicaciones válidas posibles de dígitos val como resultado de la llamada recursiva actual.
  • Imprima el valor devuelto por la función contarDeNúmeros(1, 0, 0, N) como el recuento resultante de números de N dígitos que cumplen los criterios dados.

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;
 
int dp[50][1 << 10][2];
 
// Function to find the number of N
// digit numbers such that at least
// one digit occurs more than once
int countOfNumbers(int digit, int mask,
                   bool repeated, int n)
{
    // Base Case
    if (digit == n + 1) {
        if (repeated == true) {
            return 1;
        }
        return 0;
    }
 
    // If repeated is true, then for
    // remaining positions any digit
    // can be placed
    if (repeated == true) {
        return pow(10, n - digit + 1);
    }
 
    // If the current state has already
    // been computed, then return it
    int& val = dp[digit][mask][repeated];
    if (val != -1) {
        return val;
    }
 
    // Stores the count of number for
    // the current recursive calls
    val = 0;
 
    // If current position is 1, then
    // any digit can be placed.
 
    // If n = 1, 0 can be also placed
    if (digit == 1) {
 
        for (int i = (n == 1 ? 0 : 1);
             i <= 9; ++i) {
 
            // If a digit has occurred
            // for the second time, then
            // set repeated to 1
            if (mask & (1 << i)) {
                val += countOfNumbers(
                    digit + 1, mask | (1 << i), 1, n);
            }
 
            // Otherwise
            else {
                val += countOfNumbers(
                    digit + 1, mask | (1 << i), 0, n);
            }
        }
    }
 
    // For remaining positions any
    // digit can be placed
    else {
        for (int i = 0; i <= 9; ++i) {
 
            // If a digit has occurred
            // for the second time, then
            // set repeated to 1
            if (mask & (1 << i)) {
                val += countOfNumbers(
                    digit + 1, mask | (1 << i), 1, n);
            }
            else {
                val += countOfNumbers(
                    digit + 1, mask | (1 << i), 0, n);
            }
        }
    }
 
    // Return the resultant count for
    // the current recursive call
    return val;
}
 
// Function to count all the N-digit
// numbers having at least one digit's
// occurrence more than once
void countNDigitNumber(int N)
{
    // Initialize dp array with -1
    memset(dp, -1, sizeof dp);
 
    // Function to count all possible
    // number satisfying the given
    // criteria
    cout << countOfNumbers(1, 0, 0, N);
}
 
// Driver Code
int main()
{
    int N = 2;
    countNDigitNumber(N);
 
    return 0;
}

Java

import java.util.Arrays;
 
// Java program for the above approach
 
class GFG {
 
    public static int[][][] dp = new int[50][1 << 10][2];
 
    // Function to find the number of N
    // digit numbers such that at least
    // one digit occurs more than once
    public static int countOfNumbers(int digit, int mask,
                                     int repeated, int n)
    {
       
        // Base Case
        if (digit == n + 1) {
            if (repeated == 1) {
                return 1;
            }
            return 0;
        }
 
        // If repeated is true, then for
        // remaining positions any digit
        // can be placed
        if (repeated == 1) {
            return (int) Math.pow(10, n - digit + 1);
        }
 
        // If the current state has already
        // been computed, then return it
        int val = dp[digit][mask][repeated];
        if (val != -1) {
            return val;
        }
 
        // Stores the count of number for
        // the current recursive calls
        val = 0;
 
        // If current position is 1, then
        // any digit can be placed.
 
        // If n = 1, 0 can be also placed
        if (digit == 1) {
 
            for (int i = (n == 1 ? 0 : 1); i <= 9; ++i) {
 
                // If a digit has occurred
                // for the second time, then
                // set repeated to 1
                if ((mask & (1 << i)) > 0) {
                    val += countOfNumbers(digit + 1, mask | (1 << i), 1, n);
                }
 
                // Otherwise
                else {
                    val += countOfNumbers(digit + 1, mask | (1 << i), 0, n);
                }
            }
        }
 
        // For remaining positions any
        // digit can be placed
        else {
            for (int i = 0; i <= 9; ++i) {
 
                // If a digit has occurred
                // for the second time, then
                // set repeated to 1
                if ((mask & (1 << i)) > 0) {
                    val += countOfNumbers(digit + 1, mask | (1 << i), 1, n);
                } else {
                    val += countOfNumbers(digit + 1, mask | (1 << i), 0, n);
                }
            }
        }
 
        // Return the resultant count for
        // the current recursive call
        return val;
    }
 
    // Function to count all the N-digit
    // numbers having at least one digit's
    // occurrence more than once
    public static void countNDigitNumber(int N)
    {
       
        // Initialize dp array with -1
        for (int i = 0; i < 50; i++) {
            for (int j = 0; j < 1 << 10; j++) {
                for (int k = 0; k < 2; k++) {
                    dp[i][j][k] = -1;
                }
            }
        }
       
        // Function to count all possible
        // number satisfying the given
        // criteria
        System.out.println(countOfNumbers(1, 0, 0, N));
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int N = 2;
        countNDigitNumber(N);
 
    }
}
 
// This code is contributed by gfgking.

Python3

# Python program for the above approach
 
dp = [[[-1 for i in range(2)] for i in range(1 << 10)] for i in range(50)]
 
# Function to find the number of N
# digit numbers such that at least
# one digit occurs more than once
def countOfNumbers(digit, mask, repeated, n):
    global dp
    # Base Case
    if (digit == n + 1):
        if (repeated == True):
            return 1
        return 0
 
    # If repeated is true, then for
    # remaining positions any digit
    # can be placed
    if (repeated == True):
        return pow(10, n - digit + 1)
 
    # If the current state has already
    # been computed, then return it
    val = dp[digit][mask][repeated]
    if (val != -1):
        return val
 
    # Stores the count of number for
    # the current recursive calls
    val = 4
 
    # If current position is 1, then
    # any digit can be placed.
 
    # If n = 1, 0 can be also placed
    if (digit == 1):
 
        for i in range((0 if (n==1) else 1),10):
            # If a digit has occurred
            # for the second time, then
            # set repeated to 1
            if (mask & (1 << i)):
                val += countOfNumbers(digit + 1, mask | (1 << i), 1, n)
            # Otherwise
        else:
                val += countOfNumbers(digit + 1, mask | (1 << i), 0, n)
 
    # For remaining positions any
    # digit can be placed
    else:
        for i in range(10):
            # If a digit has occurred
            # for the second time, then
            # set repeated to 1
            if (mask & (1 << i)):
                val += countOfNumbers(digit + 1, mask | (1 << i), 1, n)
        else:
                val += countOfNumbers(digit + 1, mask | (1 << i), 0, n)
 
    # Return the resultant count for
    # the current recursive call
    dp[digit][mask][repeated] = val
    return dp[digit][mask][repeated]
 
# Function to count all the N-digit
# numbers having at least one digit's
# occurrence more than once
def countNDigitNumber(N):
 
    # Function to count all possible
    # number satisfying the given
    # criteria
    print  (countOfNumbers(1, 0, 0, N))
 
# Driver Code
if __name__ == '__main__':
    N = 2
    countNDigitNumber(N)
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
 
class GFG{
 
public static int[,,] dp = new int[50, 1 << 10, 2];
 
// Function to find the number of N
// digit numbers such that at least
// one digit occurs more than once
public static int countOfNumbers(int digit, int mask,
                                 int repeated, int n)
{
     
    // Base Case
    if (digit == n + 1)
    {
        if (repeated == 1)
        {
            return 1;
        }
        return 0;
    }
 
    // If repeated is true, then for
    // remaining positions any digit
    // can be placed
    if (repeated == 1)
    {
        return(int)Math.Pow(10, n - digit + 1);
    }
 
    // If the current state has already
    // been computed, then return it
    int val = dp[digit, mask, repeated];
    if (val != -1)
    {
        return val;
    }
 
    // Stores the count of number for
    // the current recursive calls
    val = 0;
 
    // If current position is 1, then
    // any digit can be placed.
 
    // If n = 1, 0 can be also placed
    if (digit == 1)
    {
        for(int i = (n == 1 ? 0 : 1); i <= 9; ++i)
        {
             
            // If a digit has occurred
            // for the second time, then
            // set repeated to 1
            if ((mask & (1 << i)) > 0)
            {
                val += countOfNumbers(
                    digit + 1, mask | (1 << i), 1, n);
            }
 
            // Otherwise
            else
            {
                val += countOfNumbers(
                    digit + 1, mask | (1 << i), 0, n);
            }
        }
    }
 
    // For remaining positions any
    // digit can be placed
    else
    {
        for(int i = 0; i <= 9; ++i)
        {
             
            // If a digit has occurred
            // for the second time, then
            // set repeated to 1
            if ((mask & (1 << i)) > 0)
            {
                val += countOfNumbers(
                    digit + 1, mask | (1 << i), 1, n);
            }
            else
            {
                val += countOfNumbers(
                    digit + 1, mask | (1 << i), 0, n);
            }
        }
    }
 
    // Return the resultant count for
    // the current recursive call
    return val;
}
 
// Function to count all the N-digit
// numbers having at least one digit's
// occurrence more than once
public static void countNDigitNumber(int N)
{
     
    // Initialize dp array with -1
    for(int i = 0; i < 50; i++)
    {
        for(int j = 0; j < 1 << 10; j++)
        {
            for(int k = 0; k < 2; k++)
            {
                dp[i, j, k] = -1;
            }
        }
    }
 
    // Function to count all possible
    // number satisfying the given
    // criteria
    Console.Write(countOfNumbers(1, 0, 0, N));
}
 
// Driver Code
public static void Main()
{
    int N = 2;
     
    countNDigitNumber(N);
}
}
 
// This code is contributed by ukasp

Javascript

<script>
 
// JavaScript program for the above approach
 
 
let dp = new Array(50).fill(0)
    .map(() => new Array(1 << 10).fill(0)
        .map(() => new Array(2).fill(-1)));
 
// Function to find the number of N
// digit numbers such that at least
// one digit occurs more than once
function countOfNumbers(digit, mask, repeated, n) {
    // Base Case
    if (digit == n + 1) {
        if (repeated == true) {
            return 1;
        }
        return 0;
    }
 
    // If repeated is true, then for
    // remaining positions any digit
    // can be placed
    if (repeated == true) {
        return Math.pow(10, n - digit + 1);
    }
 
    // If the current state has already
    // been computed, then return it
    let val = dp[digit][mask][repeated];
    if (val != -1) {
        return val;
    }
 
    // Stores the count of number for
    // the current recursive calls
    val = 0;
 
    // If current position is 1, then
    // any digit can be placed.
 
    // If n = 1, 0 can be also placed
    if (digit == 1) {
 
        for (let i = (n == 1 ? 0 : 1);
            i <= 9; ++i) {
 
            // If a digit has occurred
            // for the second time, then
            // set repeated to 1
            if (mask & (1 << i)) {
                val += countOfNumbers(
                    digit + 1, mask | (1 << i), 1, n);
            }
 
            // Otherwise
            else {
                val += countOfNumbers(
                    digit + 1, mask | (1 << i), 0, n);
            }
        }
    }
 
    // For remaining positions any
    // digit can be placed
    else {
        for (let i = 0; i <= 9; ++i) {
 
            // If a digit has occurred
            // for the second time, then
            // set repeated to 1
            if (mask & (1 << i)) {
                val += countOfNumbers(
                    digit + 1, mask | (1 << i), 1, n);
            }
            else {
                val += countOfNumbers(
                    digit + 1, mask | (1 << i), 0, n);
            }
        }
    }
 
    // Return the resultant count for
    // the current recursive call
    return val;
}
 
// Function to count all the N-digit
// numbers having at least one digit's
// occurrence more than once
function countNDigitNumber(N) {
    // Initialize dp array with -1
 
    // Function to count all possible
    // number satisfying the given
    // criteria
    document.write(countOfNumbers(1, 0, 0, N));
}
 
// Driver Code
 
let N = 2;
countNDigitNumber(N);
 
</script>
Producción: 

9

 

Complejidad de Tiempo: O(10 * N * 2 10 * 2)
Espacio Auxiliar: O(N * 2 10 * 2)

Publicación traducida automáticamente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *