Dados dos números enteros N y K , la tarea es encontrar el conteo de números de N dígitos tal que la diferencia absoluta de los dígitos adyacentes en el número no sea mayor que K .
Ejemplos:
Entrada : N = 2, K = 1
Salida : 26
Explicación : Los números son 10, 11, 12, 21, 22, 23, 32, 33, 34, 43, 44, 45, 54, 55, 56, 65, 66 , 67, 76, 77, 78, 87, 88, 89, 98, 99
Entrada : N = 3, K = 2
Salida : 188
Enfoque ingenuo y enfoque de programación dinámica: consulte Recuento de números de N dígitos con una diferencia absoluta de dígitos adyacentes que no exceda K para obtener la solución más simple y el enfoque de programación dinámica que requiere espacio auxiliar O(N).
Enfoque de uso eficiente del espacio:
siga los pasos a continuación para optimizar el enfoque anterior:
- En el enfoque anterior, se inicializa una array 2D dp[][] donde dp[i][j] almacena el recuento de números que tienen i dígitos y terminan en j .
- Se puede observar que la respuesta para cualquier longitud i depende únicamente del conteo generado para i – 1 . Entonces, en lugar de una array 2D, inicialice una array dp[] del tamaño de todos los dígitos posibles, y para cada i hasta N , dp[j] almacena el recuento de tales números de longitud i que terminan con el dígito j .
- Inicialice otra array next[] del tamaño de todos los dígitos posibles.
- Dado que el recuento de números de un solo dígito que terminan con un valor j siempre es 1 , complete dp[] con 1 en todos los índices inicialmente.
- Itere sobre el rango [2, N] , y para cada valor en el rango i , verifique si el último dígito es j , entonces los dígitos permitidos para este lugar están en el rango (max(0, jk), min(9, j+k)) . Realice una actualización de rango:
next[l] = next[l] + dp[j]
next[r + 1] = next[r + 1] – dp[j]
donde l y r son max(0, j – k) y min(9, j + k) respectivamente.
- Una vez que se completa el paso anterior para un valor particular de i , calcule la suma del prefijo de next[] y actualice dp[] con los valores de next[] .
A continuación se muestra la implementación del enfoque anterior:
C
// C program to implement the above approach
#include <stdio.h>
// Function to find maximum between two numbers
int max(int num1, int num2)
{
return (num1 > num2 ) ? num1 : num2;
}
// Function to find minimum between two numbers
int min(int num1, int num2)
{
return (num1 > num2 ) ? num2 : num1;
}
// Function to return the count
// of such numbers
int getCount(int n, int k)
{
// For 1-digit numbers, the count
// is 10 irrespective of K
if (n == 1)
return 10;
// dp[j] stores the number
// of such i-digit numbers
// ending with j
int dp[11] = {0};
// Stores the results of length i
int next[11] = {0};
// Initialize count for
// 1-digit numbers
for(int i = 1; i <= 9; i++)
dp[i] = 1;
// Compute values for count of
// digits greater than 1
for(int i = 2; i <= n; i++)
{
for(int j = 0; j <= 9; j++)
{
// Find the range of allowed
// numbers if last digit is j
int l = max(0, (j - k));
int r = min(9, (j + k));
// Perform Range update
next[l] += dp[j];
next[r + 1] -= dp[j];
}
// Prefix sum to find actual count
// of i-digit numbers ending with j
for(int j = 1; j <= 9; j++)
next[j] += next[j - 1];
// Update dp[]
for(int j = 0; j < 10; j++)
{
dp[j] = next[j];
next[j] = 0;
}
}
// Stores the final answer
int count = 0;
for(int i = 0; i <= 9; i++)
count += dp[i];
// Return the final answer
return count;
}
// Driver Code
int main()
{
int n = 2, k = 1;
printf("%d", getCount(n, k));
}
// This code is contributed by piyush3010.
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find maximum between two numbers
int max(int num1, int num2)
{
return (num1 > num2 ) ? num1 : num2;
}
// Function to find minimum between two numbers
int min(int num1, int num2)
{
return (num1 > num2 ) ? num2 : num1;
}
// Function to return the count
// of such numbers
int getCount(int n, int k)
{
// For 1-digit numbers, the count
// is 10 irrespective of K
if (n == 1)
return 10;
// dp[j] stores the number
// of such i-digit numbers
// ending with j
int dp[11] = {0};
// Stores the results of length i
int next[11] = {0};
// Initialize count for
// 1-digit numbers
for(int i = 1; i <= 9; i++)
dp[i] = 1;
// Compute values for count of
// digits greater than 1
for(int i = 2; i <= n; i++)
{
for(int j = 0; j <= 9; j++)
{
// Find the range of allowed
// numbers if last digit is j
int l = max(0, (j - k));
int r = min(9, (j + k));
// Perform Range update
next[l] += dp[j];
next[r + 1] -= dp[j];
}
// Prefix sum to find actual count
// of i-digit numbers ending with j
for(int j = 1; j <= 9; j++)
next[j] += next[j - 1];
// Update dp[]
for(int j = 0; j < 10; j++)
{
dp[j] = next[j];
next[j] = 0;
}
}
// Stores the final answer
int count = 0;
for(int i = 0; i <= 9; i++)
count += dp[i];
// Return the final answer
return count;
}
// Driver Code
int main()
{
int n = 2, k = 1;
cout << getCount(n, k);
return 0;
}
Java
// Java Program to implement
// the above approach
import java.util.*;
class GFG {
// Function to return the count
// of such numbers
public static long getCount(
int n, int k)
{
// For 1-digit numbers, the count
// is 10 irrespective of K
if (n == 1)
return 10;
// dp[j] stores the number
// of such i-digit numbers
// ending with j
long dp[] = new long[11];
// Stores the results of length i
long next[] = new long[11];
// Initialize count for
// 1-digit numbers
for (int i = 1; i <= 9; i++)
dp[i] = 1;
// Compute values for count of
// digits greater than 1
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= 9; j++) {
// Find the range of allowed
// numbers if last digit is j
int l = Math.max(0, j - k);
int r = Math.min(9, j + k);
// Perform Range update
next[l] += dp[j];
next[r + 1] -= dp[j];
}
// Prefix sum to find actual count
// of i-digit numbers ending with j
for (int j = 1; j <= 9; j++)
next[j] += next[j - 1];
// Update dp[]
for (int j = 0; j < 10; j++) {
dp[j] = next[j];
next[j] = 0;
}
}
// Stores the final answer
long count = 0;
for (int i = 0; i <= 9; i++)
count += dp[i];
// Return the final answer
return count;
}
// Driver Code
public static void main(String[] args)
{
int n = 2, k = 1;
System.out.println(getCount(n, k));
}
}
Python3
# Python3 program to implement # the above approach # Function to return the count # of such numbers def getCount(n, K): # For 1-digit numbers, the count # is 10 irrespective of K if(n == 1): return 10 # dp[j] stores the number # of such i-digit numbers # ending with j dp = [0] * 11 # Stores the results of length i next = [0] * 11 # Initialize count for # 1-digit numbers for i in range(1, 9 + 1): dp[i] = 1 # Compute values for count of # digits greater than 1 for i in range(2, n + 1): for j in range(9 + 1): # Find the range of allowed # numbers if last digit is j l = max(0, j - k) r = min(9, j + k) # Perform Range update next[l] += dp[j] next[r + 1] -= dp[j] # Prefix sum to find actual count # of i-digit numbers ending with j for j in range(1, 9 + 1): next[j] += next[j - 1] # Update dp[] for j in range(10): dp[j] = next[j] next[j] = 0 # Stores the final answer count = 0 for i in range(9 + 1): count += dp[i] # Return the final answer return count # Driver code if __name__ == '__main__': n = 2 k = 1 print(getCount(n, k)) # This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to return the count
// of such numbers
public static long getCount(int n, int k)
{
// For 1-digit numbers, the count
// is 10 irrespective of K
if (n == 1)
return 10;
// dp[j] stores the number
// of such i-digit numbers
// ending with j
long []dp = new long[11];
// Stores the results of length i
long []next = new long[11];
// Initialize count for
// 1-digit numbers
for(int i = 1; i <= 9; i++)
dp[i] = 1;
// Compute values for count of
// digits greater than 1
for(int i = 2; i <= n; i++)
{
for(int j = 0; j <= 9; j++)
{
// Find the range of allowed
// numbers if last digit is j
int l = Math.Max(0, j - k);
int r = Math.Min(9, j + k);
// Perform Range update
next[l] += dp[j];
next[r + 1] -= dp[j];
}
// Prefix sum to find actual count
// of i-digit numbers ending with j
for(int j = 1; j <= 9; j++)
next[j] += next[j - 1];
// Update []dp
for(int j = 0; j < 10; j++)
{
dp[j] = next[j];
next[j] = 0;
}
}
// Stores the readonly answer
long count = 0;
for(int i = 0; i <= 9; i++)
count += dp[i];
// Return the readonly answer
return count;
}
// Driver Code
public static void Main(String[] args)
{
int n = 2, k = 1;
Console.WriteLine(getCount(n, k));
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// Javascript program to implement the above approach
// Function to find maximum between two numbers
function max(num1, num2)
{
return (num1 > num2 ) ? num1 : num2;
}
// Function to find minimum between two numbers
function min(num1, num2)
{
return (num1 > num2 ) ? num2 : num1;
}
// Function to return the count
// of such numbers
function getCount(n, k)
{
// For 1-digit numbers, the count
// is 10 irrespective of K
if (n == 1)
return 10;
// dp[j] stores the number
// of such i-digit numbers
// ending with j
var dp = Array(11).fill(0);
// Stores the results of length i
var next = Array(11).fill(0);
// Initialize count for
// 1-digit numbers
for(var i = 1; i <= 9; i++)
dp[i] = 1;
// Compute values for count of
// digits greater than 1
for(var i = 2; i <= n; i++)
{
for(var j = 0; j <= 9; j++)
{
// Find the range of allowed
// numbers if last digit is j
var l = Math.max(0, (j - k));
var r = Math.min(9, (j + k));
// Perform Range update
next[l] += dp[j];
next[r + 1] -= dp[j];
}
// Prefix sum to find actual count
// of i-digit numbers ending with j
for(var j = 1; j <= 9; j++)
next[j] += next[j - 1];
// Update dp[]
for(var j = 0; j < 10; j++)
{
dp[j] = next[j];
next[j] = 0;
}
}
// Stores the final answer
var count = 0;
for(var i = 0; i <= 9; i++)
count += dp[i];
// Return the final answer
return count;
}
// Driver Code
var n = 2, k = 1;
document.write( getCount(n, k));
// This code is contributed by chinmoy1997pal.
</script>
Producción:
26
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por jrishabh99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA