Dado un número entero N , la tarea es contar los números hasta N que tengan una diferencia absoluta de como máximo K entre dos dígitos adyacentes cualesquiera.
Nota: El número de enteros 0 para cualquier dígito es considerable.
Ejemplos:
Entrada: N = 20, K = 2
Salida: 15
Explicación:
Los números necesarios son 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 y 20. Observe que 14, 15, 16, 17, 18 y 19 tienen una diferencia absoluta de dígitos adyacentes mayor que K = 2 y, por lo tanto, no se cuentan.
Entrada: N = 30, K = 3
Salida: 22
Explicación:
Se aceptan todos los números hasta 30 excepto 15, 16, 17, 18, 19, 26, 27, 28, 29.
Enfoque ingenuo: la idea es iterar hasta N y verificar para todos los números que la diferencia de K existe o no. En caso afirmativo, cuéntelo; de lo contrario, omita el número y siga iterando.
Complejidad de Tiempo: O(N)
Espacio Auxiliar: O(1)
Enfoque Eficiente: Este problema se puede optimizar usando Programación Dinámica de Dígitos . Los siguientes son los estados de dp detallados para el problema dado.
- En Digit Dp, consideramos nuestro número como una secuencia de dígitos, por lo que se necesita una posición de estado, así que marque en qué estado nos encontramos actualmente. En cada llamada recursiva, intente construir la secuencia de izquierda a derecha colocando un dígito del 0 al 9 e incremente la posición.
- El dígito anterior almacena solo aquellos dígitos que tienen una diferencia absoluta de K como máximo con respecto al dígito anterior. Entonces, se necesita otro estado para el dígito anterior.
- Tight , el estado indica si el número que estamos tratando de construir ya se ha vuelto más pequeño que N, de modo que en las próximas llamadas recursivas podamos colocar cualquier dígito del 0 al 9. De lo contrario, podemos colocar hasta el dígito de N en la posición actual .
- Inicializa una variable booleana Inicio que indica si el número ha comenzado o no. Si el número aún no ha comenzado, podemos comenzar el número colocando dígitos desde 1 hasta el límite superior con respecto al apretado en la posición actual. De lo contrario, recurra hacia adelante sin comenzar el número.
- En cada llamada recursiva, establezca el dígito actual con respecto al dígito anterior de manera que la diferencia absoluta entre ellos nunca exceda K . En el caso base, devuelve 1 si alcanzó la última posición.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to get the count
// of numbers upto N having
// absolute difference at most K
// between any two adjacent digits
#include <bits/stdc++.h>
using namespace std;
// Table to store solution
// of each subproblem
long long dp[1002][10][2][2];
// Function to calculate
// all possible numbers
long long possibleNumbers(
int pos, int previous, bool tight,
bool start, string N, int K)
{
// Check if position reaches end that is
// is equal to length of N
if (pos == N.length())
return 1;
// Check if the result is
// already computed
// simply return it
if (dp[pos][previous][tight][start] != -1)
return dp[pos][previous][tight][start];
int res = 0;
// Maximum limit upto which we can place
// digit. If tight is false, means number has
// already become smaller so we can place
// any digit, otherwise N[pos]
int upper_limit
= (tight)
? (N[pos] - '0')
: 9;
int new_tight;
// Check if start is false the number
// has not started yet
if (!start) {
// Check if we do not start
// the number at pos
// then recur forward
res = possibleNumbers(
pos + 1, previous,
false, false, N, K);
// If we start the number
// we can place any digit
// from 1 to upper_limit
for (int i = 1; i <= upper_limit; i++) {
// Finding the new tight
new_tight
= (tight
&& i == upper_limit)
? 1
: 0;
res += possibleNumbers(
pos + 1, i, new_tight,
true, N, K);
}
}
// Condition if the number
// has already started
else {
// We can place digit upto
// upperbound & absolute difference
// with previous digit much
// be atmost K
for (int i = 0; i <= upper_limit; i++) {
new_tight = (tight
&& i == upper_limit)
? 1
: 0;
// Absolute difference atmost K
if (abs(i - previous) <= K)
res += possibleNumbers(
pos + 1, i,
new_tight, true, N, K);
}
}
// Store the solution
// to this subproblem
dp[pos][previous][tight][start] = res;
return dp[pos][previous][tight][start];
}
// Driver code
int main(void)
{
string N = "20";
int K = 2;
// Initialising the
// table with -1
memset(dp, -1, sizeof dp);
// Function call
cout << possibleNumbers(
0, 0, true,
false, N, K)
<< endl;
}
Java
// Java program to get the count
// of numbers upto N having
// absolute difference at most K
// between any two adjacent digits
import java.util.*;
class GFG{
// Table to store solution
// of each subproblem
static int [][][][]dp = new int[1002][10][2][2];
// Function to calculate
// all possible numbers
static int possibleNumbers(int pos, int previous,
int tight, int start,
String N, int K)
{
// Check if position reaches end
// that is equal to length of N
if (pos == N.length())
return 1;
// Check if the result is already
// computed simply return it
if (dp[pos][previous][tight][start] != -1)
return dp[pos][previous][tight][start];
int res = 0;
// Maximum limit upto which we can
// place digit. If tight is false,
// means number has already become
// smaller so we can place
// any digit, otherwise N[pos]
int upper_limit = (tight == 1) ?
(N.charAt(pos) - '0') : 9;
int new_tight;
// Check if start is false the number
// has not started yet
if (start == 0)
{
// Check if we do not start
// the number at pos
// then recur forward
res = possibleNumbers(pos + 1, previous,
0, 0, N, K);
// If we start the number
// we can place any digit
// from 1 to upper_limit
for(int i = 1; i <= upper_limit; i++)
{
// Finding the new tight
new_tight = (tight > 0 &&
i == upper_limit) ? 1 : 0;
res += possibleNumbers(pos + 1, i,
new_tight,
1, N, K);
}
}
// Condition if the number
// has already started
else
{
// We can place digit upto
// upperbound & absolute difference
// with previous digit much
// be atmost K
for(int i = 0; i <= upper_limit; i++)
{
new_tight = (tight > 0 &&
i == upper_limit) ? 1 : 0;
// Absolute difference atmost K
if (Math.abs(i - previous) <= K)
res += possibleNumbers(pos + 1, i,
new_tight, 1,
N, K);
}
}
// Store the solution
// to this subproblem
dp[pos][previous][tight][start] = res;
return dp[pos][previous][tight][start];
}
// Driver code
public static void main(String[] args)
{
String N = "20";
int K = 2;
// Initialising the
// table with -1
for(int i = 0; i < 1002; i++)
for(int j = 0; j < 10; j++)
for(int k = 0; k < 2; k++)
for(int l = 0; l < 2; l++)
dp[i][j][k][l] = -1;
// Function call
System.out.print(possibleNumbers(0, 0, 1, 0,
N, K) + "\n");
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to get the count of
# numbers upto N having absolute
# difference at most K between any
# two adjacent digits
# Table to store solution
# of each subproblem
dp = [[[[ -1 for i in range(2)]
for j in range(2)]
for i in range(10)]
for j in range(1002)]
# Function to calculate
# all possible numbers
def possibleNumber(pos, previous, tight,
start, N, K):
# Check if position reaches end
# that is equal to length of N
if(pos == len(N)):
return 1
# Check if the result is
# already computed
# simply return it
if(dp[pos][previous][tight][start] != -1):
return dp[pos][previous][tight][start]
res = 0
# Maximum limit upto which we can place
# digit. If tight is false, means number has
# already become smaller so we can place
# any digit, otherwise N[pos]
if(tight):
upper_limit = ord(N[pos]) - ord('0')
else:
upper_limit = 9
# Check if start is false the number
# has not started yet
if(not start):
# Check if we do not start
# the number at pos
# then recur forward
res = possibleNumber(pos + 1, previous,
False, False, N, K)
# If we start the number
# we can place any digit
# from 1 to upper_limit
for i in range(1, upper_limit + 1):
# Finding the new tight
if(tight and i == upper_limit):
new_tight = 1
else:
new_tight = 0
res += possibleNumber(pos + 1, i,
new_tight,
True, N, K)
# Condition if the number
# has already started
else:
# We can place digit upto
# upperbound & absolute
# difference with previous
# digit much be atmost K
for i in range(upper_limit + 1):
if(tight and i == upper_limit):
new_tight = 1
else:
new_tight = 0
# Absolute difference atmost K
if(abs(i - previous) <= K):
res += possibleNumber(pos + 1, i,
new_tight,
True, N, K)
# Store the solution to this subproblem
dp[pos][previous][tight][start] = res
return dp[pos][previous][tight][start]
# Driver code
if __name__ == '__main__':
N = "20"
K = 2
# Function call
print(possibleNumber(0, 0, True,
False, N, K))
# This code is contributed by Shivam Singh
C#
// C# program to get the count
// of numbers upto N having
// absolute difference at most K
// between any two adjacent digits
using System;
class GFG{
// Table to store solution
// of each subproblem
static int [,,,]dp = new int[1002, 10, 2, 2];
// Function to calculate
// all possible numbers
static int possibleNumbers(int pos, int previous,
int tight, int start,
String N, int K)
{
// Check if position reaches end
// that is equal to length of N
if (pos == N.Length)
return 1;
// Check if the result is already
// computed simply return it
if (dp[pos, previous, tight, start] != -1)
return dp[pos, previous, tight, start];
int res = 0;
// Maximum limit upto which we can
// place digit. If tight is false,
// means number has already become
// smaller so we can place
// any digit, otherwise N[pos]
int upper_limit = (tight == 1) ?
(N[pos] - '0') : 9;
int new_tight;
// Check if start is false the number
// has not started yet
if (start == 0)
{
// Check if we do not start
// the number at pos
// then recur forward
res = possibleNumbers(pos + 1, previous,
0, 0, N, K);
// If we start the number
// we can place any digit
// from 1 to upper_limit
for(int i = 1; i <= upper_limit; i++)
{
// Finding the new tight
new_tight = (tight > 0 &&
i == upper_limit) ? 1 : 0;
res += possibleNumbers(pos + 1, i,
new_tight,
1, N, K);
}
}
// Condition if the number
// has already started
else
{
// We can place digit upto
// upperbound & absolute difference
// with previous digit much
// be atmost K
for(int i = 0; i <= upper_limit; i++)
{
new_tight = (tight > 0 &&
i == upper_limit) ? 1 : 0;
// Absolute difference atmost K
if (Math.Abs(i - previous) <= K)
res += possibleNumbers(pos + 1, i,
new_tight, 1,
N, K);
}
}
// Store the solution
// to this subproblem
dp[pos, previous, tight, start] = res;
return dp[pos, previous, tight, start];
}
// Driver code
public static void Main(String[] args)
{
String N = "20";
int K = 2;
// Initialising the
// table with -1
for(int i = 0; i < 1002; i++)
for(int j = 0; j < 10; j++)
for(int k = 0; k < 2; k++)
for(int l = 0; l < 2; l++)
dp[i, j, k, l] = -1;
// Function call
Console.Write(possibleNumbers(0, 0, 1, 0,
N, K) + "\n");
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// Javascript program to get the count
// of numbers upto N having
// absolute difference at most K
// between any two adjacent digits
// Table to store solution
// of each subproblem
let dp = new Array(1002);
// Function to calculate
// all possible numbers
function possibleNumbers(pos, previous, tight, start, N, K)
{
// Check if position reaches end
// that is equal to length of N
if (pos == N.length)
return 1;
// Check if the result is already
// computed simply return it
if (dp[pos][previous][tight][start] != -1)
return dp[pos][previous][tight][start];
let res = 0;
// Maximum limit upto which we can
// place digit. If tight is false,
// means number has already become
// smaller so we can place
// any digit, otherwise N[pos]
let upper_limit = (tight == 1) ?
(N[pos] - '0') : 9;
let new_tight;
// Check if start is false the number
// has not started yet
if (start == 0)
{
// Check if we do not start
// the number at pos
// then recur forward
res = possibleNumbers(pos + 1, previous,
0, 0, N, K);
// If we start the number
// we can place any digit
// from 1 to upper_limit
for(let i = 1; i <= upper_limit; i++)
{
// Finding the new tight
new_tight = (tight > 0 &&
i == upper_limit) ? 1 : 0;
res += possibleNumbers(pos + 1, i,
new_tight,
1, N, K);
}
}
// Condition if the number
// has already started
else
{
// We can place digit upto
// upperbound & absolute difference
// with previous digit much
// be atmost K
for(let i = 0; i <= upper_limit; i++)
{
new_tight = (tight > 0 &&
i == upper_limit) ? 1 : 0;
// Absolute difference atmost K
if (Math.abs(i - previous) <= K)
res += possibleNumbers(pos + 1, i,
new_tight, 1,
N, K);
}
}
// Store the solution
// to this subproblem
dp[pos][previous][tight][start] = res;
return dp[pos][previous][tight][start];
}
let N = "20";
let K = 2;
// Initialising the
// table with -1
for(let i = 0; i < 1002; i++)
{
dp[i] = new Array(10);
for(let j = 0; j < 10; j++)
{
dp[i][j] = new Array(2);
for(let k = 0; k < 2; k++)
{
dp[i][j][k] = new Array(2);
for(let l = 0; l < 2; l++)
{
dp[i][j][k][l] = -1;
}
}
}
}
// Function call
document.write(possibleNumbers(0, 0, 1, 0,
N, K) + "</br>");
// This code id contributed by divyeshrsbadiya07.
</script>
Producción:
15
Complejidad Temporal: O( D * 10 * 2 * 2 * 10), considerando que N tiene D dígitos.