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:
- Si se establece el i -ésimo bit de la máscara , agregue el valor de countOfNumbers(digit + 1, mask|(1<<i), 1, N) .
- De lo contrario, agregue el valor de countOfNumbers(digit + 1, mask|(1<<i), 0, N) .
- De lo contrario, itere sobre el rango [0, 9] usando la variable i y realice los siguientes pasos:
- Si se establece el i -ésimo bit de la máscara , agregue el valor de countOfNumbers(digit + 1, mask|(1<<i), 1, N) .
- De lo contrario, agregue el valor de countOfNumbers(digit + 1, mask|(1<<i), 0, N) .
- 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