Dado un entero positivo N , la tarea es encontrar el número de todos los números de N dígitos cuyos dígitos adyacentes tienen el mismo máximo común divisor (MCD) .
Ejemplos:
Entrada: N = 2
Salida: 90
Explicación:
Todos los números de 2 dígitos cumplen la condición ya que solo hay un par de dígitos y hay 90 números de 2 dígitos.Entrada: N = 3
Salida: 457
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los números posibles de N dígitos y contar aquellos números cuyos dígitos adyacentes tengan el mismo GCD . Después de verificar todos los números, imprima el valor del conteo como el conteo total de números resultante.
Complejidad temporal: O(N *10 N )
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de la programación dinámica porque el problema anterior tiene subproblemas superpuestos y una subestructura óptima . Los subproblemas se pueden almacenar en la memorización de la tabla dp[][][] donde dp[index][prev][gcd] almacena la respuesta desde la posición del índice hasta el final, donde prev se usa para almacenar el dígito anterior del número y mcd es el MCD entre los dígitos adyacentes existentes en el número. Siga los pasos a continuación para resolver el problema:
- Inicialice una array multidimensional global dp[100][10][10] con todos los valores como -1 que almacena el resultado de cada llamada recursiva.
- Defina una función recursiva , diga countOfNumbers(index, prev, gcd, N) y realice los siguientes pasos:
- Si el valor del índice es (N + 1) , devuelve 1 como un número de N dígitos válido.
- Si el resultado del estado dp[index][prev][gcd] ya se calculó, devuelva este valor dp[index][prev][gcd] .
- Si el índice actual es 1 , se puede colocar cualquier dígito del [1 al 9] .
- Si el índice actual es mayor que 1 , se puede colocar cualquier dígito de [0-9] .
- Si el índice es mayor que 2 , se puede colocar un dígito si el mcd del dígito actual y el dígito anterior es igual al mcd de los dígitos adyacentes ya existentes.
- Después de realizar una colocación válida de dígitos, llame recursivamente a la función countOfNumbers for (index + 1) .
- Devuelve la suma de todas las ubicaciones válidas posibles de dígitos como respuesta.
- Imprime el valor devuelto por la función countOfNumbers(1, 0, 0, N) como resultado.
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; int dp[100][10][10]; // Recursive function to find the count // of all the N-digit numbers whose // adjacent digits having equal GCD int countOfNumbers(int index, int prev, int gcd, int N) { // If index is N+1 if (index == N + 1) return 1; int& val = dp[index][prev][gcd]; // If the state has already // been computed if (val != -1) return val; // Stores the total count of all // N-digit numbers val = 0; // If index = 1, any digit from // [1-9] can be placed. // If N = 0, 0 can be placed as well if (index == 1) { for (int digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) { // Update the value val val += countOfNumbers( index + 1, digit, gcd, N); } } // If index is 2, then any digit // from [0-9] can be placed else if (index == 2) { for (int digit = 0; digit <= 9; ++digit) { val += countOfNumbers( index + 1, digit, __gcd(prev, digit), N); } } // Otherwise any digit from [0-9] can // be placed if the GCD of current // and previous digit is gcd else { for (int digit = 0; digit <= 9; ++digit) { // Check if GCD of current // and previous digit is gcd if (__gcd(digit, prev) == gcd) { val += countOfNumbers( index + 1, digit, gcd, N); } } } // Return the total count return val; } // Function to find the count of all // the N-digit numbers whose adjacent // digits having equal GCD int countNumbers(int N) { // Initialize dp array with -1 memset(dp, -1, sizeof dp); // Function Call to find the // resultant count return countOfNumbers(1, 0, 0, N); } // Driver Code int main() { int N = 2; cout << countNumbers(N); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG { static int[][][] dp = new int[100][10][10]; static int _gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return _gcd(a-b, b); return _gcd(a, b-a); } // Recursive function to find the count // of all the N-digit numbers whose // adjacent digits having equal GCD static int countOfNumbers(int index, int prev, int gcd, int N) { // If index is N+1 if (index == N + 1) return 1; int val = dp[index][prev][gcd]; // If the state has already // been computed if (val != -1) return val; // Stores the total count of all // N-digit numbers val = 0; // If index = 1, any digit from // [1-9] can be placed. // If N = 0, 0 can be placed as well if (index == 1) { for (int digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) { // Update the value val val += countOfNumbers( index + 1, digit, gcd, N); } } // If index is 2, then any digit // from [0-9] can be placed else if (index == 2) { for (int digit = 0; digit <= 9; ++digit) { val += countOfNumbers( index + 1, digit, _gcd(prev, digit), N); } } // Otherwise any digit from [0-9] can // be placed if the GCD of current // and previous digit is gcd else { for (int digit = 0; digit <= 9; ++digit) { // Check if GCD of current // and previous digit is gcd if (_gcd(digit, prev) == gcd) { val += countOfNumbers( index + 1, digit, gcd, N); } } } // Return the total count return val; } // Function to find the count of all // the N-digit numbers whose adjacent // digits having equal GCD static int countNumbers(int N) { int i, j, k; // Initialize dp array with -1 for(i = 0; i < 100; i++) { for(j = 0; j < 10; j++) { for(k = 0; k < 10; k++) { dp[i][j][k] = -1; } } } // Function Call to find the // resultant count return countOfNumbers(1, 0, 0, N); } public static void main(String[] args) { int N = 2; System.out.println(countNumbers(N)); } } // This code is contributed by target_2
Python3
# Python3 program for the above approach dp = [[[-1 for i in range(10)] for j in range(10)] for k in range(100)] from math import gcd # Recursive function to find the count # of all the N-digit numbers whose # adjacent digits having equal GCD def countOfNumbers(index, prev, gcd1, N): # If index is N+1 if (index == N + 1): return 1 val = dp[index][prev][gcd1] # If the state has already # been computed if (val != -1): return val # Stores the total count of all # N-digit numbers val = 0 # If index = 1, any digit from # [1-9] can be placed. # If N = 0, 0 can be placed as well if (index == 1): digit = 0 if N == 1 else 1 while(digit <= 9): # Update the value val val += countOfNumbers(index + 1, digit, gcd1, N) digit += 1 # If index is 2, then any digit # from [0-9] can be placed elif (index == 2): for digit in range(10): val += countOfNumbers(index + 1, digit, gcd(prev, digit), N) # Otherwise any digit from [0-9] can # be placed if the GCD of current # and previous digit is gcd else: for digit in range(10): # Check if GCD of current # and previous digit is gcd if (gcd(digit, prev) == gcd): val += countOfNumbers(index + 1, digit, gcd1, N) # Return the total count return val # Function to find the count of all # the N-digit numbers whose adjacent # digits having equal GCD def countNumbers(N): # Function Call to find the # resultant count return countOfNumbers(1, 0, 0, N) # Driver Code if __name__ == '__main__': N = 2 print(countNumbers(N)) # This code is contributed by ipg2016107
C#
// C# program for the above approach using System; public class GFG { static int[,,] dp = new int[100, 10, 10]; static int _gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return _gcd(a-b, b); return _gcd(a, b-a); } // Recursive function to find the count // of all the N-digit numbers whose // adjacent digits having equal GCD static int countOfNumbers(int index, int prev, int gcd, int N) { // If index is N+1 if (index == N + 1) return 1; int val = dp[index,prev,gcd]; // If the state has already // been computed if (val != -1) return val; // Stores the total count of all // N-digit numbers val = 0; // If index = 1, any digit from // [1-9] can be placed. // If N = 0, 0 can be placed as well if (index == 1) { for (int digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) { // Update the value val val += countOfNumbers( index + 1, digit, gcd, N); } } // If index is 2, then any digit // from [0-9] can be placed else if (index == 2) { for (int digit = 0; digit <= 9; ++digit) { val += countOfNumbers( index + 1, digit, _gcd(prev, digit), N); } } // Otherwise any digit from [0-9] can // be placed if the GCD of current // and previous digit is gcd else { for (int digit = 0; digit <= 9; ++digit) { // Check if GCD of current // and previous digit is gcd if (_gcd(digit, prev) == gcd) { val += countOfNumbers( index + 1, digit, gcd, N); } } } // Return the total count return val; } // Function to find the count of all // the N-digit numbers whose adjacent // digits having equal GCD static int countNumbers(int N) { int i, j, k; // Initialize dp array with -1 for(i = 0; i < 100; i++) { for(j = 0; j < 10; j++) { for(k = 0; k < 10; k++) { dp[i,j,k] = -1; } } } // Function Call to find the // resultant count return countOfNumbers(1, 0, 0, N); } // Driver code static public void Main () { int N = 2; Console.Write(countNumbers(N)); } } // This code is contributed by shubham singh
Javascript
<script> // Javascript program for the above approach let dp = new Array(100).fill(0).map(() => new Array(10).fill(0).map(() => new Array(10).fill(-1))); // Recursive function to find the count // of all the N-digit numbers whose // adjacent digits having equal GCD function countOfNumbers(index, prev, gcd, N) { // If index is N+1 if (index == N + 1) return 1; let val = dp[index][prev][gcd]; // If the state has already // been computed if (val != -1) return val; // Stores the total count of all // N-digit numbers val = 0; // If index = 1, any digit from // [1-9] can be placed. // If N = 0, 0 can be placed as well if (index == 1) { for (let digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) { // Update the value val val += countOfNumbers( index + 1, digit, gcd, N); } } // If index is 2, then any digit // from [0-9] can be placed else if (index == 2) { for (let digit = 0; digit <= 9; ++digit) { val += countOfNumbers( index + 1, digit, __gcd(prev, digit), N); } } // Otherwise any digit from [0-9] can // be placed if the GCD of current // and previous digit is gcd else { for (let digit = 0; digit <= 9; ++digit) { // Check if GCD of current // and previous digit is gcd if (__gcd(digit, prev) == gcd) { val += countOfNumbers( index + 1, digit, gcd, N); } } } // Return the total count return val; } // Function to find the count of all // the N-digit numbers whose adjacent // digits having equal GCD function countNumbers(N) { // Function Call to find the // resultant count return countOfNumbers(1, 0, 0, N); } function __gcd(a, b) { if (b == 0) return a; return __gcd(b, a % b); } let N = 2; document.write(countNumbers(N)); // This code is contributed by gfgking. </script>
90
Complejidad de Tiempo: O(N * 1000)
Espacio Auxiliar: O(N * 10 * 10)
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA