Cuente números de N dígitos que contengan todos los dígitos posibles al menos una vez

Dado un entero positivo N, la tarea es contar el número de números de N dígitos de modo que cada dígito de [0-9] ocurra al menos una vez.  

 Ejemplos: 

Entrada: N = 10
Salida: 3265920

Entrada: N = 5
Salida: 0
Explicación:  Dado que el número de dígitos es menor que el número mínimo de dígitos requerido [0-9], la respuesta es 0.

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar sobre todos los números de N dígitos posibles y, para cada uno de esos números, verificar si todos sus dígitos satisfacen la condición requerida o no.
Complejidad temporal: O(10 ^N *N)
Espacio auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la programación dinámica , ya que tiene subproblemas superpuestos y una subestructura óptima . Los subproblemas se pueden almacenar en la tabla dp[][] usando memoization, donde dp[digit][mask] almacena la respuesta desde la posición del dígito ^th hasta el final, cuando los dígitos incluidos se representan usando una máscara. 

Siga los pasos a continuación para resolver este problema:

• Defina una función recursiva, diga countOfNumbers(digit, mask) y realice los siguientes pasos:
  • Caso base: si el valor del dígito es igual a N+1, compruebe si el valor de la máscara es igual a (1 << 10 – 1). Si se determina que es verdadero, devuelva 1 ya que se forma un número válido de N dígitos .
  • Si el resultado del estado dp[dígito][máscara] ya se calculó, devuelve este estado dp[dígito][máscara] .
  • Si la posición actual es 1 , se puede colocar cualquier dígito del [1 al 9] . Si N es igual a 1 , entonces también se puede colocar 0 .
  • Para cualquier otra posición, se puede colocar cualquier dígito de [0-9] .
  • Si se incluye un dígito particular ‘i’ , actualice la máscara como máscara = máscara | (1 << yo ).
  • Después de realizar una ubicación válida, llame recursivamente a la función countOfNumbers para el dígito índice +1.
  • Devuelve la suma de todas las ubicaciones válidas posibles de dígitos como respuesta.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Stores the dp-states
long long dp[100][1 << 10];
 
// Function to calculate the count of
// N-digit numbers that contains all
// digits from [0-9] atleast once
long long countOfNumbers(int digit,
                         int mask, int N)
{
    // If all digits are traversed
    if (digit == N + 1) {
 
        // Check if all digits are
        // included in the mask
        if (mask == (1 << 10) - 1)
            return 1;
        return 0;
    }
 
    long long& val = dp[digit][mask];
 
    // If the state has
    // already been computed
    if (val != -1)
        return val;
 
    val = 0;
 
    // If the current digit is 1, any
    // digit from [1-9] can be placed.
    // If N==1, 0 can also be placed
    if (digit == 1) {
        for (int i = (N == 1 ? 0 : 1); i <= 9; ++i) {
 
            val += countOfNumbers(digit + 1,
                                  mask | (1 << i), N);
        }
    }
 
    // For other positions, any digit
    // from [0-9] can be placed
    else {
        for (int i = 0; i <= 9; ++i) {
 
            val += countOfNumbers(digit + 1,
                                  mask | (1 << i), N);
        }
    }
 
    // Return the answer
    return val;
}
 
// Driver Code
int main()
{
    // Initializing dp array with -1.
    memset(dp, -1, sizeof dp);
 
    // Given Input
    int N = 10;
 
    // Function Call
    cout << countOfNumbers(1, 0, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
  // Stores the dp-states
  static int dp[][] = new int[100][1 << 10];
 
  // Function to calculate the count of
  // N-digit numbers that contains all
  // digits from [0-9] atleast once
  static long countOfNumbers(int digit,
                             int mask, int N)
  {
    // If all digits are traversed
    if (digit == N + 1) {
 
      // Check if all digits are
      // included in the mask
      if (mask == (1 << 10) - 1)
        return 1;
 
      return 0;
    }
 
 
    long val = dp[digit][mask];
 
    // If the state has
    // already been computed
    if (val != -1)
      return val;
 
    val = 0;
 
    // If the current digit is 1, any
    // digit from [1-9] can be placed.
    // If N==1, 0 can also be placed
    if (digit == 1) {
      for (int i = (N == 1 ? 0 : 1); i <= 9; ++i) {
 
        val += countOfNumbers(digit + 1,
                              mask | (1 << i), N);
      }
    }
 
    // For other positions, any digit
    // from [0-9] can be placed
    else {
      for (int i = 0; i <= 9; ++i) {
 
        val += countOfNumbers(digit + 1,
                              mask | (1 << i), N);
      }
    }
 
    // Return the answer
    return val;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
     
    // Initializing dp array with -1.
    for(int i =0;i<dp.length;i++)
      Arrays.fill(dp[i], -1);
     
    // Given Input
    int N = 10;
 
    // Function Call
    System.out.print(countOfNumbers(1, 0, N));
 
  }
}
 
// This code is contributed by Rajput-Ji

# Python program for the above approach
 
# Stores the dp-states
dp = [[-1 for j in range(1 << 10)]for i in range(100)]
 
# Function to calculate the count of
# N-digit numbers that contains all
# digits from [0-9] atleast once
def countOfNumbers(digit, mask, N):
 
    # If all digits are traversed
    if (digit == N + 1):
 
        # Check if all digits are
        # included in the mask
        if (mask == (1 << 10) - 1):
            return 1
        return 0
 
    val = dp[digit][mask]
 
    # If the state has
    # already been computed
    if (val != -1):
        return val
 
    val = 0
 
    # If the current digit is 1, any
    # digit from [1-9] can be placed.
    # If N==1, 0 can also be placed
    if (digit == 1):
        for i in range((0 if (N == 1) else 1),10):
            val += countOfNumbers(digit + 1, mask | (1 << i), N)
         
 
    # For other positions, any digit
    # from [0-9] can be placed
    else:
        for i in range(10):
            val += countOfNumbers(digit + 1, mask | (1 << i), N)
 
    # Return the answer
    return val
 
# Driver Code
 
# Given Input
N = 10
 
# Function Call
print(countOfNumbers(1, 0, N))
     
# This code is contributed by shinjanpatra

// C# program to implement above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // Stores the dp-states
    static long[][] dp = new long[100][];
 
    // Function to calculate the count of
    // N-digit numbers that contains all
    // digits from [0-9] atleast once
    static long countOfNumbers(int digit, int mask, int N)
    {
        // If all digits are traversed
        if (digit == N + 1) {
 
            // Check if all digits are
            // included in the mask
            if (mask == (1 << 10) - 1){
                return 1;
            }
 
            return 0;
        }
 
 
        long val = dp[digit][mask];
 
        // If the state has
        // already been computed
        if (val != -1){
            return val;
        }
 
        val = 0;
 
        // If the current digit is 1, any
        // digit from [1-9] can be placed.
        // If N==1, 0 can also be placed
        if (digit == 1) {
            for (int i = (N == 1 ? 0 : 1) ; i <= 9 ; ++i) {
 
                val += countOfNumbers(digit + 1, mask | (1 << i), N);
            }
        }
        // For other positions, any digit
        // from [0-9] can be placed
        else {
            for (int i = 0; i <= 9; ++i) {
 
                val += countOfNumbers(digit + 1, mask | (1 << i), N);
            }
        }
 
        dp[digit][mask] = val;
        // Return the answer
        return val;
    }
 
 
    // Driver Code
    public static void Main(string[] args){
         
        // Initializing dp array with -1.
        for(int i = 0 ; i < dp.Length ; i++){
            dp[i] = new long[1 << 10];
            for(int j = 0 ; j < (1 << 10) ; j++){
                dp[i][j] = -1;
            }
        }
         
        // Given Input
        int N = 10;
 
        // Function Call
        Console.Write(countOfNumbers(1, 0, N));
 
    }
}
 
// This code is contributed by subhamgoyal2014.

<script>
 
// JavaScript program for the above approach
 
// Stores the dp-states
let dp = new Array(100);
for (let i = 0; i < 100; i++) {
    dp[i] = new Array(1 << 10).fill(-1);
}
 
// Function to calculate the count of
// N-digit numbers that contains all
// digits from [0-9] atleast once
function countOfNumbers(digit, mask, N)
{
    // If all digits are traversed
    if (digit == N + 1) {
 
        // Check if all digits are
        // included in the mask
        if (mask == (1 << 10) - 1)
            return 1;
        return 0;
    }
 
    let val = dp[digit][mask];
 
    // If the state has
    // already been computed
    if (val != -1)
        return val;
 
    val = 0;
 
    // If the current digit is 1, any
    // digit from [1-9] can be placed.
    // If N==1, 0 can also be placed
    if (digit == 1) {
        for (let i = (N == 1 ? 0 : 1); i <= 9; ++i) {
 
            val += countOfNumbers(digit + 1,
                                  mask | (1 << i), N);
        }
    }
 
    // For other positions, any digit
    // from [0-9] can be placed
    else {
        for (let i = 0; i <= 9; ++i) {
 
            val += countOfNumbers(digit + 1,
                                  mask | (1 << i), N);
        }
    }
 
    // Return the answer
    return val;
}
 
// Driver Code
 
    // Given Input
    let N = 10;
 
    // Function Call
    document.write(countOfNumbers(1, 0, N));
     
</script>

3265920

Complejidad de tiempo: O( N ² *2 ¹⁰ )
Espacio auxiliar: O( N*2 ¹⁰ )