Recuento de números de N dígitos que tienen una diferencia absoluta entre dígitos adyacentes como K

Posted on by Rudeus Greyrat

Dados dos enteros N y K. La tarea es contar todos los enteros positivos con longitud N que tengan una diferencia absoluta entre dígitos adyacentes igual a K .

Ejemplos:

Entrada: N = 4, K = 8
Salida: 3
Explicación: La diferencia absoluta entre cada dígito consecutivo de cada número es 8. Los tres números posibles son 8080, 1919 y 9191.

Entrada: N = 2, K = 0
Salida: 9
Explicación: 11, 22, 33, 44, 55, 66, 77, 88, 99. La diferencia absoluta entre cada dígito consecutivo de cada número es 0.

 

Enfoque: El enfoque se basa en la recursividad . Itere sobre los dígitos [1, 9], y para cada dígito, cuente el número de N dígitos que tiene una diferencia de dígito absoluto como K usando recursividad. Los siguientes casos llegan a la llamada de función recursiva.

  • Caso base: para todos los números enteros de un solo dígito, es decir, N = 1, incremente el recuento de respuestas.
  • Llamada recursiva: si sumar el dígito K al dígito de la unidad del número formado hasta ahora (num) no excede 9, entonces llame recursivamente disminuyendo N y haciendo num = (num*10 + num%10 + K) .

if(num % 10 + K ≤ 9) 
   recursive_function(10 * num + (num % 10 + K), N – 1); 

  • Si el valor de K es distinto de cero después de todas las llamadas recursivas y si num % 10 ≥ K , vuelva a llamar recursivamente disminuyendo N y actualice num a (10*num + num%10 – K).

if(num % 10 ≥ K) 
    función_recursiva(10 * num + num % 10 – K, N – 1)

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;
 
// To store the count of numbers
int countNums = 0;
 
// Function that recursively finds the
// possible numbers and append into ans
void checkUtil(int num, int K, int N)
{
    // Base Case
    if (N == 1) {
        countNums++;
        return;
    }
 
    // Check the sum of last digit and k
    // less than or equal to 9 or not
    if ((num % 10 + K) <= 9)
        checkUtil(10 * num +
                  (num % 10 + K), K, N - 1);
 
    // If K = 0, then subtraction and
    // addition does not make any
    // difference
    if (K) {
         
        // If unit's digit greater than K
        if ((num % 10 - K) >= 0)
            checkUtil(10 * num +
                      num % 10 - K, K, N - 1);
    }
}
 
// Function to call checkUtil function
// for every integer from 1 to 9
void check(int K, int N)
{
    // Loop to check for
    // all digits from 1 to 9
    for (int i = 1; i <= 9; i++) {
        checkUtil(i, K, N);
    }
}
 
// Driver Code
int main()
{
    // Given N and K
    int N = 4, K = 8;
    check(K, N);
 
    // Count total possible numbers
    cout << countNums << endl;
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// To store the count of numbers
static int countNums = 0;
 
// Function that recursively finds the
// possible numbers and append into ans
static void checkUtil(int num, int K, int N)
{
   
    // Base Case
    if (N == 1) {
        countNums++;
        return;
    }
 
    // Check the sum of last digit and k
    // less than or equal to 9 or not
    if ((num % 10 + K) <= 9)
        checkUtil(10 * num +
                  (num % 10 + K), K, N - 1);
 
    // If K = 0, then subtraction and
    // addition does not make any
    // difference
    if (K>0) {
         
        // If unit's digit greater than K
        if ((num % 10 - K) >= 0)
            checkUtil(10 * num +
                      num % 10 - K, K, N - 1);
    }
}
 
// Function to call checkUtil function
// for every integer from 1 to 9
static void check(int K, int N)
{
   
    // Loop to check for
    // all digits from 1 to 9
    for (int i = 1; i <= 9; i++) {
        checkUtil(i, K, N);
    }
}
 
// Driver Code
public static void main(String[] args)
{
   
    // Given N and K
    int N = 4, K = 8;
    check(K, N);
 
    // Count total possible numbers
    System.out.print(countNums +"\n");
}
}
 
// This code contributed by shikhasingrajput

Python3

# Python program for the above approach
 
# To store the count of numbers
countNums = 0;
 
# Function that recursively finds the
# possible numbers and append into ans
def checkUtil(num, K, N):
    global countNums;
     
    # Base Case
    if (N == 1):
        countNums += 1;
        return;
 
    # Check the sum of last digit and k
    # less than or equal to 9 or not
    if ((num % 10 + K) <= 9):
        checkUtil(10 * num + (num % 10 + K), K, N - 1);
 
    # If K = 0, then subtraction and
    # addition does not make any
    # difference
    if (K > 0):
 
        # If unit's digit greater than K
        if ((num % 10 - K) >= 0):
            checkUtil(10 * num + num % 10 - K, K, N - 1);
 
# Function to call checkUtil function
# for every integer from 1 to 9
def check(K, N):
   
    # Loop to check for
    # all digits from 1 to 9
    for i in range(1,10):
        checkUtil(i, K, N);
 
# Driver Code
if __name__ == '__main__':
    # Given N and K
    N = 4;
    K = 8;
    check(K, N);
 
    # Count total possible numbers
    print(countNums);
 
# This code is contributed by shikhasingrajput

C#

// C# program for the above approach
using System;
 
class GFG{
 
// To store the count of numbers
static int countNums = 0;
 
// Function that recursively finds the
// possible numbers and append into ans
static void checkUtil(int num, int K, int N)
{
     
    // Base Case
    if (N == 1)
    {
        countNums++;
        return;
    }
 
    // Check the sum of last digit and k
    // less than or equal to 9 or not
    if ((num % 10 + K) <= 9)
        checkUtil(10 * num +
                 (num % 10 + K), K, N - 1);
 
    // If K = 0, then subtraction and
    // addition does not make any
    // difference
    if (K > 0)
    {
         
        // If unit's digit greater than K
        if ((num % 10 - K) >= 0)
            checkUtil(10 * num +
                      num % 10 - K, K, N - 1);
    }
}
 
// Function to call checkUtil function
// for every integer from 1 to 9
static void check(int K, int N)
{
     
    // Loop to check for
    // all digits from 1 to 9
    for(int i = 1; i <= 9; i++)
    {
        checkUtil(i, K, N);
    }
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given N and K
    int N = 4, K = 8;
    check(K, N);
 
    // Count total possible numbers
    Console.Write(countNums + "\n");
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
      // JavaScript code for the above approach
 
      // To store the count of numbers
      let countNums = 0;
 
      // Function that recursively finds the
      // possible numbers and append into ans
      function checkUtil(num, K, N)
      {
       
          // Base Case
          if (N == 1) {
              countNums++;
              return;
          }
 
          // Check the sum of last digit and k
          // less than or equal to 9 or not
          if ((num % 10 + K) <= 9)
              checkUtil(10 * num +
                  (num % 10 + K), K, N - 1);
 
          // If K = 0, then subtraction and
          // addition does not make any
          // difference
          if (K) {
 
              // If unit's digit greater than K
              if ((num % 10 - K) >= 0)
                  checkUtil(10 * num +
                      num % 10 - K, K, N - 1);
          }
      }
 
      // Function to call checkUtil function
      // for every integer from 1 to 9
      function check(K, N)
      {
       
          // Loop to check for
          // all digits from 1 to 9
          for (let i = 1; i <= 9; i++) {
              checkUtil(i, K, N);
          }
      }
 
      // Driver Code
 
      // Given N and K
      let N = 4, K = 8;
      check(K, N);
 
      // Count total possible numbers
      document.write(countNums + '<br>');
 
// This code is contributed by Potta Lokesh
  </script>
Producción

3

Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por Code_r 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 *