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 .
- Defina una función recursiva noncoprimeCount(i,bound,prev,allZeros) realizando los siguientes pasos.
- 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.
- 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.
- Si el resultado del estado dp[i][bound][anterior][allZeros] ya se calculó, devuelva el valor almacenado en dp[i][bound][anterior][allZeros].
- 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:
- Si el índice actual es 0, coloque cualquier dígito en la primera posición.
- 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 .
- 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).
- 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:
C++
#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; }
Java
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
Python3
# 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.
C#
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
// 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 10 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 10 N * 2 * 10 * 2)
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA