Dado un número entero N y una array maxDigit[] , la tarea es contar todos los números distintos de N dígitos de modo que el dígito i no aparezca más de maxDigit[i] veces. Dado que el conteo puede ser muy grande, imprímalo módulo 10 9 + 7 .
Ejemplos:
Entrada: N = 2, maxDigit[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Salida: 90
Explicación:
Cualquier dígito no puede aparecer más de una vez consecutivamente. Por lo tanto, los números [00, 11, 22, 33, 44, 55, 66, 77, 88, 99] no son válidos.
Por lo tanto, los números totales sin restricciones son 10 × 10 = 100.
Por lo tanto, la cuenta es 100 – 10 = 90.Entrada: N = 3, maxDigit[] = {2, 1, 1, 1, 1, 2, 1, 1, 1, 2}
Salida: 864
Enfoque ingenuo: el enfoque más simple es iterar sobre todos los números de N dígitos y contar aquellos números que satisfacen las condiciones dadas. Después de verificar todos los números, imprima el conteo total módulo 10 9 + 7 .
Complejidad temporal: O(N*10 N )
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar el concepto de programación dinámica de dígitos . Los estados de DP para este problema se explican a continuación:
- En Digit-DP, la idea es construir un número de izquierda a derecha colocando un dígito [0, 9] en cada posición. Por lo tanto, para realizar un seguimiento de la posición actual, se requiere tener un estado de posición . Este estado tendrá valores posibles de 0 a (N – 1) .
- De acuerdo con la pregunta, un dígito i no puede aparecer más de maxDigit[i] veces consecutivas, por lo tanto, realice un seguimiento del dígito previamente completado. Por lo tanto, se requiere un estado anterior . Este estado tendrá valores posibles de 0 a 9 .
- Se requiere un conteo estatal que proporcione la cantidad de veces que un dígito puede aparecer consecutivamente. Este estado tendrá valores posibles de 1 a maxDigit[i] .
Siga los pasos a continuación para resolver este problema:
- La primera posición puede tener cualquier dígito sin restricciones.
- Desde la segunda posición en adelante, mantenga un registro del dígito llenado anteriormente y su cuenta dada hasta la cual puede aparecer consecutivamente.
- Si aparece el mismo dígito en la siguiente posición, disminuya su conteo y si este conteo llega a cero, simplemente ignore este dígito en la siguiente llamada recursiva.
- Si aparece un dígito diferente en la siguiente posición, actualice su conteo de acuerdo con el valor dado en maxDigit[] .
- En cada una de las llamadas recursivas anteriores , cuando se genera el número resultante, incremente el conteo para ese número.
- Después de los pasos anteriores, imprima el valor del recuento total como resultado.
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;
// Macros for modulus
#define MOD 1000000007
// DP array for memoization
int dp[5005][12][12];
// Utility function to count N digit
// numbers with digit i not appearing
// more than max_digit[i] consecutively
int findCountUtil(int N, int maxDigit[],
int position = 0,
int previous = 0,
int count = 1)
{
// If number with N digits
// is generated
if (position == N) {
return 1;
}
// Create a reference variable
int& ans = dp[position][previous][count];
// Check if the current state is
// already computed before
if (ans != -1) {
return ans;
}
// Initialize ans as zero
ans = 0;
for (int i = 0; i <= 9; ++i) {
// Check if count of previous
// digit has reached zero or not
if (count == 0 && previous != i) {
// Fill current position
// only with digits that
// are unequal to previous digit
ans = (ans
+ (findCountUtil(N, maxDigit,
position + 1, i,
maxDigit[i] - 1))
% MOD)
% MOD;
}
else if (count != 0) {
// If by placing the same digit
// as previous on the current
// position, decrement count by 1
// Else set the value of count
// for this new digit
// accordingly from max_digit[]
ans = (ans
+ (findCountUtil(
N, maxDigit, position + 1, i,
(previous == i && position != 0)
? count - 1
: maxDigit[i] - 1))
% MOD)
% MOD;
}
}
return ans;
}
// Function to count N digit numbers
// with digit i not appearing more
// than max_digit[i] consecutive times
void findCount(int N, int maxDigit[])
{
// Stores the final count
int ans = findCountUtil(N, maxDigit);
// Print the total count
cout << ans;
}
// Driver Code
int main()
{
int N = 2;
int maxDigit[10] = { 1, 1, 1, 1, 1,
1, 1, 1, 1, 1 };
// Initialize the dp array with -1
memset(dp, -1, sizeof(dp));
// Function Call
findCount(N, maxDigit);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Macros for modulus
static int MOD = 1000000007;
// DP array for memoization
static int dp[][][] = new int[5005][12][12];
// Utility function to count N digit
// numbers with digit i not appearing
// more than max_digit[i] consecutively
static int findCountUtil(int N, int maxDigit[],
int position,
int previous,
int count)
{
// If number with N digits
// is generated
if (position == N)
{
return 1;
}
// Create a reference variable
int ans = dp[position][previous][count];
// Check if the current state is
// already computed before
if (ans != -1)
{
return ans;
}
// Initialize ans as zero
ans = 0;
for(int i = 0; i <= 9; ++i)
{
// Check if count of previous
// digit has reached zero or not
if (count == 0 && previous != i)
{
// Fill current position
// only with digits that
// are unequal to previous digit
ans = (ans + (findCountUtil(
N, maxDigit, position + 1, i,
maxDigit[i] - 1)) % MOD) % MOD;
}
else if (count != 0)
{
// If by placing the same digit
// as previous on the current
// position, decrement count by 1
// Else set the value of count
// for this new digit
// accordingly from max_digit[]
ans = (ans + (findCountUtil(
N, maxDigit, position + 1, i,
(previous == i && position != 0) ?
count - 1 : maxDigit[i] - 1)) % MOD) % MOD;
}
}
return ans;
}
// Function to count N digit numbers
// with digit i not appearing more
// than max_digit[i] consecutive times
static void findCount(int N, int maxDigit[])
{
int position = 0;
int previous = 0;
int count = 1;
// Stores the final count
int ans = findCountUtil(N, maxDigit, position,
previous, count);
// Print the total count
System.out.println(ans);
}
// Driver Code
public static void main (String[] args)
{
int N = 2;
int[] maxDigit = { 1, 1, 1, 1, 1,
1, 1, 1, 1, 1 };
// Initialize the dp array with -1
// Fill each row with -1.
for(int[][] row : dp)
{
for(int[] rowColumn : row)
{
Arrays.fill(rowColumn, -1);
}
}
// Function Call
findCount(N, maxDigit);
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python3 program for the above approach # Macros for modulus # DP array for memoization dp = [[[ -1 for i in range(5005)] for i in range(12) ] for i in range(12)] # Utility function to count N digit # numbers with digit i not appearing # more than max_digit[i] consecutively def findCountUtil(N, maxDigit, position ,previous ,count): global dp # If number with N digits # is generated if (position == N): return 1 # Create a reference variable ans = dp[position][previous][count] # Check if the current state is # already computed before if (ans != -1): return ans # Initialize ans as zero ans = 0 for i in range(10): # Check if count of previous # digit has reached zero or not if (count == 0 and previous != i): # Fill current position # only with digits that # are unequal to previous digit ans = (ans + (findCountUtil(N, maxDigit, position + 1, i, maxDigit[i] - 1)) % 1000000007)% 1000000007 elif (count != 0): # If by placing the same digit # as previous on the current # position, decrement count by 1 # Else set the value of count # for this new digit # accordingly from max_digit[] ans = (ans + (findCountUtil(N, maxDigit, position + 1, i, count - 1 if (previous == i and position != 0) else maxDigit[i] - 1)) % 1000000007)% 1000000007 dp[position][previous][count] = ans return ans # Function to count N digit numbers # with digit i not appearing more # than max_digit[i] consecutive times def findCount(N, maxDigit): # Stores the final count ans = findCountUtil(N, maxDigit, 0, 0, 1) # Print the total count print (ans) # Driver Code if __name__ == '__main__': N = 2 maxDigit = [1, 1, 1, 1, 1,1, 1, 1, 1, 1] # Function Call findCount(N, maxDigit) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System;
using System.Collections.Generic;
public class GFG{
// Macros for modulus
static int MOD = 1000000007;
// DP array for memoization
static int [,,]dp = new int[5005, 12, 12];
// Utility function to count N digit
// numbers with digit i not appearing
// more than max_digit[i] consecutively
static int findCountUtil(int N, int []maxDigit,
int position,
int previous,
int count)
{
// If number with N digits
// is generated
if (position == N)
{
return 1;
}
// Create a reference variable
int ans = dp[position, previous, count];
// Check if the current state is
// already computed before
if (ans != -1)
{
return ans;
}
// Initialize ans as zero
ans = 0;
for(int i = 0; i <= 9; ++i)
{
// Check if count of previous
// digit has reached zero or not
if (count == 0 && previous != i)
{
// Fill current position
// only with digits that
// are unequal to previous digit
ans = (ans + (findCountUtil(
N, maxDigit, position + 1, i,
maxDigit[i] - 1)) % MOD) % MOD;
}
else if (count != 0)
{
// If by placing the same digit
// as previous on the current
// position, decrement count by 1
// Else set the value of count
// for this new digit
// accordingly from max_digit[]
ans = (ans + (findCountUtil(
N, maxDigit, position + 1, i,
(previous == i && position != 0) ?
count - 1 : maxDigit[i] - 1)) % MOD) % MOD;
}
}
return ans;
}
// Function to count N digit numbers
// with digit i not appearing more
// than max_digit[i] consecutive times
static void findCount(int N, int []maxDigit)
{
int position = 0;
int previous = 0;
int count = 1;
// Stores the readonly count
int ans = findCountUtil(N, maxDigit, position,
previous, count);
// Print the total count
Console.WriteLine(ans);
}
// Driver Code
public static void Main(String[] args)
{
int N = 2;
int[] maxDigit = { 1, 1, 1, 1, 1,
1, 1, 1, 1, 1 };
// Initialize the dp array with -1
// Fill each row with -1.
for(int i = 0; i < dp.GetLength(0); i++)
{
for (int j = 0; j < dp.GetLength(1); j++)
{
for (int k = 0; k < dp.GetLength(2); k++)
dp[i, j, k] = -1;
}
}
// Function Call
findCount(N, maxDigit);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Macros for modulus
let MOD = 1000000007;
// DP array for memoization
let dp = new Array(5005);
for(let i = 0; i < 12; i++)
{
dp[i] = new Array(12);
for(let j = 0; j < 12; j++)
{
dp[i][j] = new Array(12);
for(let k = 0; k < 12; k++)
{
dp[i][j][k] = -1;
}
}
}
// Utility function to count N digit
// numbers with digit i not appearing
// more than max_digit[i] consecutively
function findCountUtil(N, maxDigit, position, previous, count)
{
// If number with N digits
// is generated
if (position == N)
{
return 1;
}
// Create a reference variable
let ans = dp[position][previous][count];
// Check if the current state is
// already computed before
if (ans != -1)
{
return ans;
}
// Initialize ans as zero
ans = 0;
for(let i = 0; i <= 9; ++i)
{
// Check if count of previous
// digit has reached zero or not
if (count == 0 && previous != i)
{
// Fill current position
// only with digits that
// are unequal to previous digit
ans = (ans + (findCountUtil(
N, maxDigit, position + 1, i,
maxDigit[i] - 1)) % MOD) % MOD;
}
else if (count != 0)
{
// If by placing the same digit
// as previous on the current
// position, decrement count by 1
// Else set the value of count
// for this new digit
// accordingly from max_digit[]
ans = (ans + (findCountUtil(
N, maxDigit, position + 1, i,
(previous == i && position != 0) ?
count - 1 : maxDigit[i] - 1)) % MOD) % MOD;
}
}
return ans;
}
// Function to count N digit numbers
// with digit i not appearing more
// than max_digit[i] consecutive times
function findCount(N, maxDigit)
{
let position = 0;
let previous = 0;
let count = 1;
// Stores the final count
let ans = findCountUtil(N, maxDigit, position, previous, count);
// Print the total count
document.write(ans);
}
let N = 2;
let maxDigit = [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ];
// Function Call
findCount(N, maxDigit);
// This code is contributed by decode2207.
</script>
Producción:
90
Complejidad de tiempo: O(N*10*10)
Espacio auxiliar: O(N*10*10)