Dado un número entero N , la tarea es contar la cantidad de números de N dígitos de modo que cada dígito, excepto el primero y el segundo, sea menor o igual que la diferencia absoluta de los dos dígitos anteriores.
Ejemplos:
Entrada: N = 1
Salida: 10
Explicación: Todos los números del [0 al 9] son válidos porque el número de dígitos es 1.Entrada: N = 3
Salida: 375
Enfoque ingenuo: el enfoque más simple es iterar 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 anterior o no.
Complejidad temporal: O(10 N *N)
Espacio auxiliar: O(1)
Enfoque eficiente: en el enfoque eficiente, se construyen todos los números posibles en lugar de verificar las condiciones en un rango de números. Esto se puede lograr con la ayuda de la programación dinámica porque tiene subproblemas superpuestos y una subestructura óptima . Los subproblemas se pueden almacenar en la tabla dp[][][] utilizando la memorización donde dp[dígito][anterior1][anterior2] almacena la respuesta desde la posición del dígito-ésimo hasta el final, cuando el dígito anterior seleccionado es el anterior1 y el el segundo dígito más anterior seleccionado es prev2.
Siga los pasos a continuación para resolver el problema:
- Defina una función recursiva countOfNumbers(digit, prev1, prev2) realizando los siguientes pasos.
- Consultar los casos base . Si el valor del dígito es igual a N+1 , devuelve 1 ya que se forma un número válido de N dígitos .
- Si el resultado del estado dp[dígito][anterior1][anterior2] ya se calculó, devuelve este estado dp[dígito][anterior1][anterior2 ].
- Si el dígito actual es 1 , se puede colocar cualquier dígito del [1 al 9] . Si N=1 , entonces también se puede colocar 0 .
- Si el dígito actual es 2 , entonces se puede colocar cualquier dígito del [0 al 9] .
- De lo contrario, se puede colocar cualquier número de [0-(abs(anterior1-anterior2))] en la posición actual.
- Después de realizar una ubicación válida, llame recursivamente a la función countOfNumbers para index digit+1 .
- Devuelve la suma de todas las ubicaciones válidas posibles de dígitos como respuesta.
A continuación se muestra el código para el enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
long long dp[50][10][10];
// Function to count N digit numbers whose
// digits are less than or equal to the
// absolute difference of previous two digits
long long countOfNumbers(int digit, int prev1,
int prev2, int N)
{
// If all digits are traversed
if (digit == N + 1)
return 1;
// If the state has already been computed
if (dp[digit][prev1][prev2] != -1)
return dp[digit][prev1][prev2];
dp[digit][prev1][prev2] = 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 j = (N == 1 ? 0 : 1);
j <= 9; ++j) {
dp[digit][prev1][prev2]
+= countOfNumbers(digit + 1,
j, prev1, N);
}
}
// If the current digit is 2, any
// digit from [0-9] can be placed
else if (digit == 2) {
for (int j = 0; j <= 9; ++j) {
dp[digit][prev1][prev2]
+= countOfNumbers(
digit + 1, j, prev1, N);
}
}
// For other digits, any digit
// from 0 to abs(prev1 - prev2) can be placed
else {
for (int j = 0; j <= abs(prev1 - prev2); ++j) {
dp[digit][prev1][prev2]
+= countOfNumbers(digit + 1, j, prev1, N);
}
}
// Return the answer
return dp[digit][prev1][prev2];
}
// Driver code
int main()
{
// Initializing dp array with -1.
memset(dp, -1, sizeof dp);
// Input
int N = 3;
// Function call
cout << countOfNumbers(1, 0, 0, N) << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static int dp[][][] = new int[50][10][10];
static void initialize()
{
for(int i = 0; i < 50; i++)
{
for(int j = 0; j < 10; j++)
{
for(int k = 0; k < 10; k++)
{
dp[i][j][k] = -1;
}
}
}
}
// Function to count N digit numbers whose
// digits are less than or equal to the
// absolute difference of previous two digits
static int countOfNumbers(int digit, int prev1,
int prev2, int N)
{
// If all digits are traversed
if (digit == N + 1)
return 1;
// If the state has already been computed
if (dp[digit][prev1][prev2] != -1)
return dp[digit][prev1][prev2];
dp[digit][prev1][prev2] = 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 j = (N == 1 ? 0 : 1);
j <= 9; ++j)
{
dp[digit][prev1][prev2] += countOfNumbers(
digit + 1, j, prev1, N);
}
}
// If the current digit is 2, any
// digit from [0-9] can be placed
else if (digit == 2)
{
for(int j = 0; j <= 9; ++j)
{
dp[digit][prev1][prev2] += countOfNumbers(
digit + 1, j, prev1, N);
}
}
// For other digits, any digit
// from 0 to abs(prev1 - prev2) can be placed
else
{
for(int j = 0; j <= Math.abs(prev1 - prev2); ++j)
{
dp[digit][prev1][prev2] += countOfNumbers(
digit + 1, j, prev1, N);
}
}
// Return the answer
return dp[digit][prev1][prev2];
}
// Driver Code
public static void main(String[] args)
{
initialize();
// Input
int N = 3;
// Function call
System.out.print(countOfNumbers(1, 0, 0, N));
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python3 program for the above approach dp = [[[-1 for i in range(10)] for j in range(10)] for k in range(50)] # Function to count N digit numbers whose # digits are less than or equal to the # absolute difference of previous two digits def countOfNumbers(digit, prev1, prev2, N): # If all digits are traversed if (digit == N + 1): return 1 # If the state has already been computed if (dp[digit][prev1][prev2] != -1): return dp[digit][prev1][prev2] dp[digit][prev1][prev2] = 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): term = 0 if N == 1 else 1 for j in range(term, 10, 1): dp[digit][prev1][prev2] += countOfNumbers( digit + 1, j, prev1, N) # If the current digit is 2, any # digit from [0-9] can be placed elif (digit == 2): for j in range(10): dp[digit][prev1][prev2] += countOfNumbers( digit + 1, j, prev1, N) # For other digits, any digit # from 0 to abs(prev1 - prev2) can be placed else: for j in range(abs(prev1 - prev2) + 1): dp[digit][prev1][prev2] += countOfNumbers( digit + 1, j, prev1, N) # Return the answer return dp[digit][prev1][prev2] # Driver code if __name__ == '__main__': # Input N = 3 # Function call print(countOfNumbers(1, 0, 0, N)) # This code is contributed by ipg2016107
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static int [,,]dp = new int[50, 10, 10];
static void initialize()
{
for(int i = 0; i < 50; i++)
{
for(int j = 0; j < 10; j++)
{
for(int k = 0; k < 10; k++)
{
dp[i, j, k] = -1;
}
}
}
}
// Function to count N digit numbers whose
// digits are less than or equal to the
// absolute difference of previous two digits
static int countOfNumbers(int digit, int prev1,
int prev2, int N)
{
// If all digits are traversed
if (digit == N + 1)
return 1;
// If the state has already been computed
if (dp[digit, prev1, prev2] != -1)
return dp[digit, prev1, prev2];
dp[digit, prev1, prev2] = 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 j = (N == 1 ? 0 : 1);
j <= 9; ++j)
{
dp[digit, prev1, prev2] += countOfNumbers(
digit + 1, j, prev1, N);
}
}
// If the current digit is 2, any
// digit from [0-9] can be placed
else if (digit == 2)
{
for(int j = 0; j <= 9; ++j)
{
dp[digit, prev1, prev2] += countOfNumbers(
digit + 1, j, prev1, N);
}
}
// For other digits, any digit
// from 0 to abs(prev1 - prev2)
// can be placed
else
{
for(int j = 0; j <= Math.Abs(prev1 - prev2); ++j)
{
dp[digit, prev1, prev2] += countOfNumbers(
digit + 1, j, prev1, N);
}
}
// Return the answer
return dp[digit, prev1, prev2];
}
// Driver code
public static void Main()
{
initialize();
// Input
int N = 3;
// Function call
Console.Write(countOfNumbers(1, 0, 0, N));
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// JavaScript program for the above approach
var dp = Array.from(Array(50), ()=>Array(10));
for(var i =0; i<10; i++)
for(var j =0; j<10; j++)
dp[i][j] = new Array(10).fill(-1);
// Function to count N digit numbers whose
// digits are less than or equal to the
// absolute difference of previous two digits
function countOfNumbers(digit, prev1, prev2, N)
{
// If all digits are traversed
if (digit == N + 1)
return 1;
// If the state has already been computed
if (dp[digit][prev1][prev2] != -1)
return dp[digit][prev1][prev2];
dp[digit][prev1][prev2] = 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 (var j = (N == 1 ? 0 : 1);
j <= 9; ++j) {
dp[digit][prev1][prev2]
+= countOfNumbers(digit + 1,
j, prev1, N);
}
}
// If the current digit is 2, any
// digit from [0-9] can be placed
else if (digit == 2) {
for (var j = 0; j <= 9; ++j) {
dp[digit][prev1][prev2]
+= countOfNumbers(
digit + 1, j, prev1, N);
}
}
// For other digits, any digit
// from 0 to abs(prev1 - prev2) can be placed
else {
for (var j = 0; j <= Math.abs(prev1 - prev2); ++j) {
dp[digit][prev1][prev2]
+= countOfNumbers(digit + 1, j, prev1, N);
}
}
// Return the answer
return dp[digit][prev1][prev2];
}
// Driver code
// Input
var N = 3;
// Function call
document.write( countOfNumbers(1, 0, 0, N));
</script>
Producción:
375
Complejidad de tiempo: O(N * 10 3 )
Espacio auxiliar: O(N * 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