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>
Producción:
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