Dado un entero positivo N , la tarea es contar el número de números de N dígitos donde cada dígito del número es la media de sus dos dígitos adyacentes.
Ejemplos:
Entrada: N = 1
Salida: 10
Explicación: Todos los números del 0 al 9 cumplen la condición dada ya que solo hay un dígito.Entrada: N = 2
Salida: 90
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es iterar sobre todos los números posibles de N dígitos y contar esos números donde cada dígito es la media de los dos dígitos adyacentes. Después de verificar todos los números, imprima el valor de conteo como resultado.
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 tabla dp[][][] utilizando la memorización donde dp[dígito][prev1][prev2] almacena la respuesta desde la posición del dígito th hasta el final, cuando el dígito anterior seleccionado es prev1 y el segundo el dígito anterior seleccionado es prev2 . Siga los pasos a continuación para resolver el problema:
- Defina una función recursiva, digamos countOfNumbers(digit, prev1, prev2) realizando los siguientes pasos.
- Si el valor del dígito es igual a N + 1 , devuelva 1 ya que se forma un número válido de N dígitos .
- Si el resultado del estado dp[dígito][anterior1][anterior2] ya se calculó, devuelva este estado dp[dígito][anterior1][anterior2].
- Si el dígito actual es 1 , entonces se puede colocar cualquier dígito de [1, 9] . Si N = 1 , entonces también se puede colocar 0 .
- Si el dígito actual es 2 , entonces se puede colocar cualquier dígito de [0, 9] .
- De lo contrario, considere los tres números prev1 , prev2 y el dígito actual que se colocará y que aún no se ha decidido. Entre estos tres números, prev1 debe ser la media de prev2 y el dígito actual . Por lo tanto, dígito actual = (2*prev1) – prev2. Si actual >= 0 y actual <= 9 entonces podemos colocarlo en la posición dada. De lo contrario devuelve 0.
- Dado que la media implica la división de enteros, (actual + 1) también se puede colocar en la posición actual si (actual + 1) >= 0 y (actual + 1) ≤ 9 .
- Después de realizar una ubicación válida, llame recursivamente a la función countOfNumbers para el índice (dígito + 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];
// Function to find number of 'N'
// digit numbers such that the element
// is mean of sum of its adjacent digits
int countOfNumbers(int digit, int prev1,
int prev2, int n)
{
// If digit = n + 1, a valid
// n-digit number has been formed
if (digit == n + 1) {
return 1;
}
// If the state has
// already been computed
int& val = dp[digit][prev1][prev2];
if (val != -1) {
return val;
}
val = 0;
// If current position is 1,
// then any digit from [1-9]
// can be placed.
// If n = 1, 0 can be also placed.
if (digit == 1) {
for (int i = (n == 1 ? 0 : 1); i <= 9; ++i) {
val += countOfNumbers(
digit + 1, i, prev1, n);
}
}
// If current position is 2,
// then any digit from [1-9]
// can be placed.
else if (digit == 2) {
for (int i = 0; i <= 9; ++i) {
val += countOfNumbers(
digit + 1, i, prev1, n);
}
}
else {
// previous digit selected is the mean.
int mean = prev1;
// mean = (current + prev2) / 2
// current = (2 * mean) - prev2
int current = (2 * mean) - prev2;
// Check if current and current+1
// can be valid placements
if (current >= 0 and current <= 9)
val += countOfNumbers(digit + 1, current, prev1,
n);
if ((current + 1) >= 0 and (current + 1) <= 9)
val += countOfNumbers(digit + 1, current + 1,
prev1, n);
}
// return answer
return val;
}
// Driver code
int main()
{
// Initializing dp array with -1.
memset(dp, -1, sizeof dp);
// Given Input
int n = 2;
// Function call
cout << countOfNumbers(1, 0, 0, n) << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static int dp[][][] = new int[100][10][10];
// Function to find number of 'N'
// digit numbers such that the element
// is mean of sum of its adjacent digits
static int countOfNumbers(int digit, int prev1,
int prev2, int n)
{
// If digit = n + 1, a valid
// n-digit number has been formed
if (digit == n + 1) {
return 1;
}
// If the state has
// already been computed
int val = dp[digit][prev1][prev2];
if (val != -1) {
return val;
}
val = 0;
// If current position is 1,
// then any digit from [1-9]
// can be placed.
// If n = 1, 0 can be also placed.
if (digit == 1) {
for (int i = (n == 1 ? 0 : 1); i <= 9; ++i) {
val += countOfNumbers(
digit + 1, i, prev1, n);
}
}
// If current position is 2,
// then any digit from [1-9]
// can be placed.
else if (digit == 2) {
for (int i = 0; i <= 9; ++i) {
val += countOfNumbers(
digit + 1, i, prev1, n);
}
}
else {
// previous digit selected is the mean.
int mean = prev1;
// mean = (current + prev2) / 2
// current = (2 * mean) - prev2
int current = (2 * mean) - prev2;
// Check if current and current+1
// can be valid placements
if (current >= 0 && current <= 9)
val += countOfNumbers(digit + 1, current, prev1,
n);
if ((current + 1) >= 0 && (current + 1) <= 9)
val += countOfNumbers(digit + 1, current + 1,
prev1, n);
}
// return answer
return val;
}
// Driver code
public static void main(String[] args)
{
// Initializing dp array with -1.
for(int i = 0; i < 100; i++)
{
for(int j = 0; j < 10; j++)
{
for(int k = 0; k < 10; k++)
{
dp[i][j][k] = -1;
}
}
}
// Given Input
int n = 2;
// Function call
System.out.println(countOfNumbers(1, 0, 0, n));
}
}
// This code is contributed by sanjoy_62.
Python3
# python program for the above approach dp = [[[-1 for i in range(10)] for col in range(20)] for row in range(100)] # Function to find number of 'N' # digit numbers such that the element # is mean of sum of its adjacent digits def countOfNumbers(digit, prev1, prev2, n): # If digit = n + 1, a valid # n-digit number has been formed if (digit == n + 1): return 1 # If the state has # already been computed val = dp[digit][prev1][prev2] if (val != -1): return val val = 0 # If current position is 1, # then any digit from [1-9] # can be placed. # If n = 1, 0 can be also placed. if (digit == 1): start = 1 if(n == 1): start = 0 for i in range(start, 10): val += countOfNumbers(digit + 1, i, prev1, n) # If current position is 2, # then any digit from [1-9] # can be placed. elif (digit == 2): for i in range(0, 10): val += countOfNumbers(digit + 1, i, prev1, n) else: # previous digit selected is the mean. mean = prev1 # // mean = (current + prev2) / 2 # // current = (2 * mean) - prev2 current = (2 * mean) - prev2 # Check if current and current+1 # can be valid placements if (current >= 0 and current <= 9): val += countOfNumbers(digit + 1, current, prev1, n) if ((current + 1) >= 0 and (current + 1) <= 9): val += countOfNumbers(digit + 1, current + 1, prev1, n) # return answer return val # Driver code # Initializing dp array with -1. # Given Input n = 2 # Function call print(countOfNumbers(1, 0, 0, n)) #cThis code is contributed by amreshkumar3
C#
// C# program for the above approach
using System;
class GFG{
static int[,,] dp = new int[100, 10, 10];
// Function to find number of 'N'
// digit numbers such that the element
// is mean of sum of its adjacent digits
static int countOfNumbers(int digit, int prev1,
int prev2, int n)
{
// If digit = n + 1, a valid
// n-digit number has been formed
if (digit == n + 1) {
return 1;
}
// If the state has
// already been computed
int val = dp[digit, prev1, prev2];
if (val != -1) {
return val;
}
val = 0;
// If current position is 1,
// then any digit from [1-9]
// can be placed.
// If n = 1, 0 can be also placed.
if (digit == 1) {
for (int i = (n == 1 ? 0 : 1); i <= 9; ++i) {
val += countOfNumbers(
digit + 1, i, prev1, n);
}
}
// If current position is 2,
// then any digit from [1-9]
// can be placed.
else if (digit == 2) {
for (int i = 0; i <= 9; ++i) {
val += countOfNumbers(
digit + 1, i, prev1, n);
}
}
else {
// previous digit selected is the mean.
int mean = prev1;
// mean = (current + prev2) / 2
// current = (2 * mean) - prev2
int current = (2 * mean) - prev2;
// Check if current and current+1
// can be valid placements
if (current >= 0 && current <= 9)
val += countOfNumbers(digit + 1, current, prev1,
n);
if ((current + 1) >= 0 && (current + 1) <= 9)
val += countOfNumbers(digit + 1, current + 1,
prev1, n);
}
// return answer
return val;
}
// Driver Code
static public void Main ()
{
// Initializing dp array with -1.
for(int i = 0; i < 100; i++)
{
for(int j = 0; j < 10; j++)
{
for(int k = 0; k < 10; k++)
{
dp[i, j, k] = -1;
}
}
}
// Given Input
int n = 2;
// Function call
Console.Write(countOfNumbers(1, 0, 0, n));
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// javascript program for the above approach
var dp = Array(100).fill().map(() =>Array(10).fill().map(()=>Array(10).fill(-1)));
// Function to find number of 'N'
// digit numbers such that the element
// is mean of sum of its adjacent digits
function countOfNumbers(digit , prev1,
prev2 , n)
{
// If digit = n + 1, a valid
// n-digit number has been formed
if (digit == n + 1) {
return 1;
}
// If the state has
// already been computed
var val = dp[digit][prev1][prev2];
if (val != -1) {
return val;
}
val = 0;
// If current position is 1,
// then any digit from [1-9]
// can be placed.
// If n = 1, 0 can be also placed.
if (digit == 1) {
for (var i = (n == 1 ? 0 : 1); i <= 9; ++i) {
val += countOfNumbers(
digit + 1, i, prev1, n);
}
}
// If current position is 2,
// then any digit from [1-9]
// can be placed.
else if (digit == 2) {
for (var i = 0; i <= 9; ++i) {
val += countOfNumbers(
digit + 1, i, prev1, n);
}
}
else {
// previous digit selected is the mean.
var mean = prev1;
// mean = (current + prev2) / 2
// current = (2 * mean) - prev2
var current = (2 * mean) - prev2;
// Check if current and current+1
// can be valid placements
if (current >= 0 && current <= 9)
val += countOfNumbers(digit + 1, current, prev1,
n);
if ((current + 1) >= 0 && (current + 1) <= 9)
val += countOfNumbers(digit + 1, current + 1,
prev1, n);
}
// return answer
return val;
}
// Driver code
// Given Input
var n = 2;
// Function call
document.write(countOfNumbers(1, 0, 0, n));
// This code is contributed by gauravrajput1
</script>
Producción
90
Complejidad de tiempo: O(N × 10 2 )
Espacio auxiliar: O(N × 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