Conteo de números de N dígitos con una diferencia absoluta de dígitos adyacentes que no exceda K | conjunto 2

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *