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: 3265920Entrada: 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++
// 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
// 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
Python3
# 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#
// 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.
Javascript
<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>
Producción:
3265920
Complejidad de tiempo: O( N 2 *2 10 )
Espacio auxiliar: O( N*2 10 )
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA