Cuente números de un rango dado cuyos dígitos adyacentes no sean coprimos

Dado un número entero N , la tarea de imprimir los números de conteo del rango [1, N] cuyos dígitos adyacentes no son coprimos. 

Se dice que dos números A y B son coprimos si el MCD de los dos números es 1.

Ejemplos:

Entrada: N = 30
Salida: 15
Explicación: Los números de [1, 30] que tienen dígitos adyacentes no coprimos son {1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 22, 24, 26, 28, 30}.

Entrada: N = 10000
Salida: 1361

Enfoque ingenuo: el enfoque más simple para resolver el problema es iterar sobre el rango de 1 a N , y para cada número del rango, verificar si el GCD de sus dígitos adyacentes es igual a 1 o no y actualizar la respuesta en consecuencia.

Complejidad de tiempo: O(NlogN) 
Espacio auxiliar: O(1) .

Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de la programación dinámica porque tiene subproblemas superpuestos y una subestructura óptima. Los subproblemas se pueden almacenar en la tabla dp[][][][] usando memoization donde dp[i][bound][prev][allZeros] almacena la respuesta desde la ‘i’ésima posición hasta el final donde el límite es una variable booleana lo que asegura que el número no exceda N , prev almacena el dígito anterior seleccionado , allZeros es una variable booleana utilizada para verificar si todos los dígitos seleccionados hasta ahora son 0 o no . 

1. Defina una función recursiva noncoprimeCount(i,bound,prev,allZeros) realizando los siguientes pasos.
   1. Convierta el límite N en una string para que se itere solo en la longitud de la string y no en el límite real de N.
   2. Verifique el caso base, que es si toda la string se atraviesa por completo (i == N) , luego devuelva 1 como un número válido en el rango [1, N] que se ha construido.
   3. Si el resultado del estado dp[i][bound][anterior][allZeros] ya se calculó, devuelva el valor almacenado en dp[i][bound][anterior][allZeros].
   4. En la posición actual ‘i’ se puede colocar cualquier número de [0, 9]. Mientras coloca un dígito, asegúrese de que el número no exceda ‘R’ con la ayuda de la variable bind . También verifique si el GCD del dígito actual y el dígito anterior (que se almacena en anterior ) es mayor que 1. Aquí hay dos casos extremos:
      1. Si el índice actual es 0, coloque cualquier dígito en la primera posición.
      2. Si todos los dígitos llenados hasta ahora son ceros, es decir, todos los ceros son verdaderos, entonces es válido colocar 1 en la posición actual a pesar de GCD (0, 1) = 1 , ya que es el dígito más significativo. Luego establezca allZeros en false .
   5. Después de colocar un dígito válido en la posición actual, llame recursivamente a la función noncoprimeCount para el elemento en el índice (i + 1).
   6. Devuelve la suma de todas las ubicaciones válidas posibles de dígitos como respuesta.

• Después de completar los pasos anteriores, imprima el valor de nocoprimeCount(0) como resultado.

A continuación se muestra la implementación del enfoque anterior: 

#include <bits/stdc++.h>
using namespace std;
 
int dp[100][2][10][2];
 
// Function to count numbers whose
// adjacent digits are not co-prime
int noncoprimeCount(int i, int N, string& S,
                    bool bound, int prev,
                    bool allZeros)
{
    // Base Case
    // If the entire string
    // is traversed
    if (i == N)
        return 1;
 
    int& val = dp[i][bound][prev][allZeros];
 
    // If the subproblem has
    // already been computed
    if (val != -1)
        return val;
 
    int cnt = 0;
 
    for (int j = 0; j <= (bound ? (S[i] - '0') : 9); ++j) {
 
        // A digit can be placed at
        // the current position if:
 
        // GCD of current and previous
        // digits is not equal to 1
        if ((__gcd(j, prev) != 1)
 
            // Current position is 0
            || (i == 0)
 
            // All encountered digits
            // until now are 0s
            || allZeros == 1) {
 
            cnt += noncoprimeCount(
                i + 1, N, S, bound
                                 & (j == (S[i] - '0')),
                j,
                allZeros & (j == 0));
        }
    }
 
    // Return the total
    // possible valid numbers
    return val = cnt;
}
 
// Function to count numbers whose
// adjacent digits are not co-prime
void noncoprimeCountUtil(int R)
{
    // Convert R to string.
    string S = to_string(R);
 
    // Length of string
    int N = S.length();
 
    // Initialize dp array with -1
    memset(dp, -1, sizeof dp);
 
    // Function call with initial values of
    // bound, allZeros, previous as 1, 1, 0
    int ans = noncoprimeCount(0, N, S, 1, 0, 1);
 
    // Subtract 1 from the answer, as 0 is included
    cout << ans - 1 << endl;
}
 
// Driver Code
int main()
{
    // Input
    int N = 10000;
    // Function call
    noncoprimeCountUtil(N);
 
    return 0;
}

import java.util.*;
 
class GFG{
 
static int [][][][]dp = new int[100][2][10][2];
static int __gcd(int a, int b) 
{ 
    return b == 0? a:__gcd(b, a % b);    
}
// Function to count numbers whose
// adjacent digits are not co-prime
static int noncoprimeCount(int i, int N, char []S,
                    int bound, int prev,
                    int allZeros)
{
    // Base Case
    // If the entire String
    // is traversed
    if (i == N)
        return 1;
 
    int val = dp[i][bound][prev][allZeros];
 
    // If the subproblem has
    // already been computed
    if (val != -1)
        return val;
 
    int cnt = 0;
 
    for (int j = 0; j <= (bound!=0 ? (S[i] - '0') : 9); ++j) {
 
        // A digit can be placed at
        // the current position if:
 
        // GCD of current and previous
        // digits is not equal to 1
        if ((__gcd(j, prev) != 1)
 
            // Current position is 0
            || (i == 0)
 
            // All encountered digits
            // until now are 0s
            || allZeros == 1) {
 
            cnt += noncoprimeCount(
                i + 1, N, S, bound!=0
                                 & (j == (S[i] - '0'))?1:0,
                j,
                (allZeros!=0 & (j == 0))?1:0);
        }
    }
 
    // Return the total
    // possible valid numbers
    return val = cnt;
}
 
// Function to count numbers whose
// adjacent digits are not co-prime
static void noncoprimeCountUtil(int R)
{
    // Convert R to String.
    String S = String.valueOf(R);
 
    // Length of String
    int N = S.length();
 
    // Initialize dp array with -1
    for (int i = 0; i < 100; i++)
         for (int j = 0; j < 2; j++)
             for (int k = 0; k < 10; k++)
                 for (int l = 0; l < 2; l++)
                     dp[i][j][k][l] = -1;
 
    // Function call with initial values of
    // bound, allZeros, previous as 1, 1, 0
    int ans = noncoprimeCount(0, N, S.toCharArray(), 1, 0, 1);
 
    // Subtract 1 from the answer, as 0 is included
    System.out.print(ans - 1 +"\n");
}
 
// Driver Code
public static void main(String[] args)
{
    // Input
    int N = 10000;
    // Function call
    noncoprimeCountUtil(N);
 
}
}
 
// This code contributed by shikhasingrajput

# importing "math" for mathematical operations
import math
 
dp = []
 
# Function to count numbers whose
# adjacent digits are not co-prime
def noncoprimeCount(i, N, S,
                    bound, prev, allZeros):
    # Base Case
    # If the entire string
    # is traversed
    if (i == N):
        return 1
    val = dp[i][bound][prev][allZeros]
 
    # if the subproblem has
    # already been computed
    if (val != -1):
        return val
 
    cnt = 0
    limit = 9
    if(bound != 0):
        limit = ord(S[i])-48
    limit += 1
    for j in range(0, limit):
 
        # A digit can be placed at
        # the current position if:
 
        # GCD of current and previous
        # digits is not equal to 1
        if ((math.gcd(j, prev) != 1)
 
            # Current position is 0
            or (i == 0)
 
            # All encountered digits
            # until now are 0s
                or allZeros == 1):
 
            cnt += noncoprimeCount(
                i + 1, N, S, bound
                & (j == (ord(S[i]) - 48)),
                j,
                allZeros & (j == 0))
 
    # Return the total
    # possible valid numbers
    val = cnt
    return val
 
# Function to count numbers whose
# adjacent digits are not co-prime
def noncoprimeCountUtil(R):
   
    # Convert R to string.
    S = str(R)
 
    # Length of string
    N = len(S)
 
    # Initialize dp array with -1
    for i in range(0, 100):
        dp.append([])
        for j in range(0, 2):
            dp[i].append([])
            for k in range(0, 10):
                dp[i][j].append([])
                for l in range(0, 2):
                    dp[i][j][k].append(-1)
 
    # Function call with initial values of
    # bound, allZeros, previous as 1, 1, 0
    ans = noncoprimeCount(0, N, S, 1, 0, 1)
 
    # Subtract 1 from the answer, as 0 is included
    print(ans-1)
 
# Driver Code
# Input
N = 10000
 
# Function call
noncoprimeCountUtil(N)
 
# This code is contributed by rj13to.

using System;
 
class GFG{
 
static int[,,,] dp = new int[100, 2, 10, 2];
 
static int __gcd(int a, int b)
{
    return b == 0 ? a : __gcd(b, a % b);
}
 
// Function to count numbers whose
// adjacent digits are not co-prime
static int noncoprimeCount(int i, int N, char[] S, int bound,
                           int prev, int allZeros)
{
     
    // Base Case
    // If the entire String
    // is traversed
    if (i == N)
        return 1;
 
    int val = dp[i, bound, prev, allZeros];
 
    // If the subproblem has
    // already been computed
    if (val != -1)
        return val;
 
    int cnt = 0;
 
    for(int j = 0;
            j <= (bound != 0 ? (S[i] - '0') : 9); ++j)
    {
         
        // A digit can be placed at
        // the current position if:
 
        // GCD of current and previous
        // digits is not equal to 1
        if ((__gcd(j, prev) != 1)
         
                // Current position is 0
                || (i == 0)
 
                // All encountered digits
                // until now are 0s
                || allZeros == 1)
        {
            cnt += noncoprimeCount(i + 1, N, S, bound != 0 &
                                  (j == (S[i] - '0')) ? 1 : 0, j,
                           (allZeros != 0 & (j == 0)) ? 1 : 0);
        }
    }
 
    // Return the total
    // possible valid numbers
    return val = cnt;
}
 
// Function to count numbers whose
// adjacent digits are not co-prime
static void noncoprimeCountUtil(int R)
{
     
    // Convert R to String.
    String S = String.Join("", R);
 
    // Length of String
    int N = S.Length;
 
    // Initialize dp array with -1
    for(int i = 0; i < 100; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 10; k++)
                for(int l = 0; l < 2; l++)
                    dp[i, j, k, l] = -1;
 
    // Function call with initial values of
    // bound, allZeros, previous as 1, 1, 0
    int ans = noncoprimeCount(0, N, S.ToCharArray(), 1, 0, 1);
 
    // Subtract 1 from the answer, as 0 is included
    Console.Write(ans - 1 + "\n");
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Input
    int N = 10000;
     
    // Function call
    noncoprimeCountUtil(N);
}
}
 
// This code is contributed by umadevi9616

// Javascript code to implement the approach
 
  var dp = new Array(100)
 
  // Function for converting
  // bool to Int (True -> 1, False -> 0)
  function boolToInt(x){
      if(x){
          return 1
      }
      return 0
  }
 
  // Function for finding gcd of two numbers
  function __gcd(x, y) {
      x = Math.abs(x);
      y = Math.abs(y);
      while(y) {
        var t = y;
        y = x % y;
        x = t;
      }
      return x;
  }
 
 
  // Function to count numbers whose
  // adjacent digits are not co-prime
  function noncoprimeCount(i, N, S, bound, prev, allZeros)
  {
      // Base Case
      // If the entire string
      // is traversed
      if (i == N){
          return 1
      }
 
      var val = dp[i][bound][prev][allZeros]
 
      // If the subproblem has
      // already been computed
      if (val != -1){
          return val
      }
 
      var cnt = 0;
 
      for (let j = 0 ; j <= (bound == 1 ? (S[i] - '0') : 9) ; ++j) {
 
          // A digit can be placed at
          // the current position if:
 
          // GCD of current and previous
          // digits is not equal to 1
          if ((__gcd(j, prev) != 1)
 
              // Current position is 0
              || (i == 0)
 
              // All encountered digits
              // until now are 0s
              || allZeros == 1)
          {
 
              cnt += noncoprimeCount(i + 1, N, S, bound & boolToInt(j == (S[i] - '0')), j, allZeros & boolToInt(j == 0));
          }
      }
 
      dp[i][bound][prev][allZeros] = cnt
      // Return the total
      // possible valid numbers
      return cnt;
  }
 
  // Function to count numbers whose
  // adjacent digits are not co-prime
  function noncoprimeCountUtil(R)
  {
      // Convert R to string.
      var S = R.toString()
 
      // Length of string
      var N = S.length
 
      // Initialize dp array with -1
      for(let i = 0 ; i < 100 ; i++){
          dp[i] = new Array(2)
          for(let j = 0 ; j < 2 ; j++){
              dp[i][j] = new Array(10)
              for(let k = 0 ; k < 10 ; k++){
                  dp[i][j][k] = new Array(2)
                  for(let l = 0 ; l < 2 ; l++){
                      dp[i][j][k][l] = -1
                  }
              }
          }
      }
 
      // Function call with initial values of
      // bound, allZeros, previous as 1, 1, 0
      var ans = noncoprimeCount(0, N, S, 1, 0, 1);
 
      // Subtract 1 from the answer, as 0 is included
      console.log(ans - 1)
  }
 
  // Input
  var N = 10000;
  // Function call
  noncoprimeCountUtil(N);
   
  // This code is contributed by subhamgoyal2014.

1361

Complejidad temporal: O(log ₁₀ N * 2 * 10 * 2 * 10). El factor adicional de 10 surge cuando todos los dígitos [0, 9] se iteran en cada llamada recursiva.
Espacio Auxiliar: O(log ₁₀ N * 2 * 10 * 2)