Dado un entero positivo N , la tarea es encontrar el número de números de N dígitos tal que cada dígito sea más pequeño que sus dígitos adyacentes.
Ejemplos:
Entrada: N = 1
Salida: 10
Explicación: Todos los números del [0 al 9] cumplen la condición ya que solo hay un dígito.Entrada: N = 3
Salida: 525
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es iterar sobre todos los números de N dígitos posibles y, para cada uno de esos números, verificar si todos sus dígitos satisfacen los criterios dados o no. Si se encuentra que es cierto, entonces cuente estos números. Después de verificar todos los números, imprima el conteo total obtenido.
Complejidad temporal: O(10 N *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 tiene subproblemas superpuestos y una subestructura óptima. Los subproblemas se pueden almacenar en la tabla dp[][][] mediante memorización donde dp[i][anterior][signo] almacena el resultado desde la i -ésima posición hasta el final, cuando el dígito anterior seleccionado es anterior y la variable El signo se utiliza para indicar si el dígito actual debe ser menor o mayor que el dígito anterior. Siga los pasos a continuación para resolver el problema:
- Defina una función recursiva , digamos, countOfNumbers(digit, prev, sign) con tres parámetros: digit, sign y prev.
- Compruebe los casos base , es decir, si el valor de i es igual a N , devuelva 1 cuando se forme un número válido de N dígitos.
- Inicialice una variable, digamos, val = 0 , para almacenar todos los recuentos posibles de números de N dígitos.
- Si i es 0 , entonces se puede colocar cualquier dígito de [1 – 9] , y también si N = 1 , entonces también se puede colocar 0 .
- Si i es 1 , cualquier dígito del [0 al 9] se puede colocar de manera que el dígito actual no sea igual al anterior.
- Si el valor del signo es 1 , coloque el dígito actual de manera que sea menor que el dígito anterior y cambie el signo a 0 para la siguiente llamada recursiva.
- Si el valor del signo es 0 , coloque el dígito actual de manera que sea mayor que el dígito anterior y cambie el signo a 1 para la siguiente llamada recursiva.
- 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 resultado de cada llamada recursiva actual .
- Después de los pasos anteriores, imprima el valor devuelto por la función contarDeNúmeros(0, N, 0, 0) como el conteo resultante.
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;
// Declaration of dp table
int dp[100][10][2];
// Function to find the count of all N
// digit numbers such that all the digit
// is less than its adjacent digits
int solve(int i, int n, int prev, bool sign)
{
// Base Case:
// If i = n, then return 1 as valid
// number has been formed
if (i == n) {
return 1;
}
int& val = dp[i][prev][sign];
// If the state has already been
// computed, then return it
if (val != -1)
return val;
// Stores the total count of ways
// for the current recursive call
val = 0;
// If i = 0, any digit from [1-9]
// can be placed and also if N = 1
//, then 0 can also be placed
if (i == 0) {
for (int digit = (n == 1 ? 0 : 1);
digit <= 9;
++digit) {
val += solve(i + 1, n,
digit, sign);
}
}
// If i = 1, any digit from [0-9]
// can be placed such that digit
// is not equal to previous digit
else if (i == 1) {
for (int digit = 0; digit <= 9;
++digit) {
// If the current digit is
// not same as the prev
if (digit != prev) {
val += solve(i + 1, n, digit,
(digit > prev));
}
}
}
else {
// Place the current digit such
// that it is less than the
// previous digit
if (sign == 1) {
for (int digit = prev - 1;
digit >= 0;
--digit) {
val += solve(i + 1, n,
digit, 0);
}
}
// Place current digit such
// that it is more than the
// previous digit
else {
for (int digit = prev + 1;
digit <= 9;
++digit) {
val += solve(i + 1, n,
digit, 1);
}
}
}
// Return the resultant total count
return val;
}
// Function to find all N-digit numbers
// satisfying the given criteria
void countNdigitNumber(int N)
{
// Initialize an array dp[] with
// all elements as -1
memset(dp, -1, sizeof dp);
// Function call to count all
// possible ways
cout << solve(0, N, 0, 0);
}
// Driver Code
int main()
{
int N = 3;
countNdigitNumber(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class MyClass
{
// Declaration of dp table
static int[][][] dp = new int[100][10][2];
// Function to find the count of all N
// digit numbers such that all the digit
// is less than its adjacent digits
static int solve(int i, int n, int prev, int sign)
{
// Base Case:
// If i = n, then return 1 as valid
// number has been formed
if (i == n) {
return 1;
}
int val = dp[i][prev][sign];
// If the state has already been
// computed, then return it
if (val != -1)
return val;
// Stores the total count of ways
// for the current recursive call
val = 0;
// If i = 0, any digit from [1-9]
// can be placed and also if N = 1
//, then 0 can also be placed
if (i == 0) {
for (int digit = (n == 1 ? 0 : 1);
digit <= 9;
++digit) {
val += solve(i + 1, n,
digit, sign);
}
}
// If i = 1, any digit from [0-9]
// can be placed such that digit
// is not equal to previous digit
else if (i == 1) {
for (int digit = 0; digit <= 9;
++digit) {
// If the current digit is
// not same as the prev
if (digit != prev) {
val += solve(i + 1, n, digit,((digit > prev)?1:0));
}
}
}
else {
// Place the current digit such
// that it is less than the
// previous digit
if (sign == 1) {
for (int digit = prev - 1;
digit >= 0;
--digit) {
val += solve(i + 1, n,
digit, 0);
}
}
// Place current digit such
// that it is more than the
// previous digit
else {
for (int digit = prev + 1;
digit <= 9;
++digit) {
val += solve(i + 1, n,
digit, 1);
}
}
}
// Return the resultant total count
return val;
}
// Function to find all N-digit numbers
// satisfying the given criteria
static void countNdigitNumber(int N)
{
// Initialize an array dp[] with
// all elements as -1
for (int[][] row : dp)
{
for (int[] rowColumn : row)
{
Arrays.fill(rowColumn, -1);
}
}
// Function call to count all
// possible ways
System.out.println(solve(0, N, 0, 0));
}
// Driver Code
public static void main(String args[])
{
int N = 3;
countNdigitNumber(N);
}
}
// This code is contributed by SoumikMondal
Python3
# python 3 program for the above approach # Declaration of dp table dp = [[[-1 for x in range(2)] for y in range(10)] for z in range(100)] # Function to find the count of all N # digit numbers such that all the digit # is less than its adjacent digits def solve(i, n, prev, sign): # Base Case: # If i = n, then return 1 as valid # number has been formed if (i == n): return 1 val = dp[i][prev][sign] # If the state has already been # computed, then return it if (val != -1): return val # Stores the total count of ways # for the current recursive call val = 0 # If i = 0, any digit from [1-9] # can be placed and also if N = 1 # , then 0 can also be placed if (i == 0): if (n == 1): digit = 0 else: digit = 1 while digit <= 9: val += solve(i + 1, n, digit, sign) digit += 1 # If i = 1, any digit from [0-9] # can be placed such that digit # is not equal to previous digit elif (i == 1): for digit in range(10): # If the current digit is # not same as the prev if (digit != prev): val += solve(i + 1, n, digit, (digit > prev)) else: # Place the current digit such # that it is less than the # previous digit if (sign == 1): for digit in range(prev - 1, -1, -1): val += solve(i + 1, n, digit, 0) # Place current digit such # that it is more than the # previous digit else: for digit in range(prev + 1, 10): val += solve(i + 1, n, digit, 1) # Return the resultant total count return val # Function to find all N-digit numbers # satisfying the given criteria def countNdigitNumber(N): # Initialize an array dp[] with # all elements as -1 # Function call to count all # possible ways print(solve(0, N, 0, 0)) # Driver Code if __name__ == "__main__": N = 3 countNdigitNumber(N) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class MyClass
{
// Declaration of dp table
static int[,,] dp = new int[100,10,2];
// Function to find the count of all N
// digit numbers such that all the digit
// is less than its adjacent digits
static int solve(int i, int n, int prev, int sign)
{
// Base Case:
// If i = n, then return 1 as valid
// number has been formed
if (i == n) {
return 1;
}
int val = dp[i,prev,sign];
// If the state has already been
// computed, then return it
if (val != -1)
return val;
// Stores the total count of ways
// for the current recursive call
val = 0;
// If i = 0, any digit from [1-9]
// can be placed and also if N = 1
//, then 0 can also be placed
if (i == 0) {
for (int digit = (n == 1 ? 0 : 1);
digit <= 9;
++digit) {
val += solve(i + 1, n,
digit, sign);
}
}
// If i = 1, any digit from [0-9]
// can be placed such that digit
// is not equal to previous digit
else if (i == 1) {
for (int digit = 0; digit <= 9;
++digit) {
// If the current digit is
// not same as the prev
if (digit != prev) {
val += solve(i + 1, n, digit,((digit > prev)?1:0));
}
}
}
else {
// Place the current digit such
// that it is less than the
// previous digit
if (sign == 1) {
for (int digit = prev - 1;
digit >= 0;
--digit) {
val += solve(i + 1, n,
digit, 0);
}
}
// Place current digit such
// that it is more than the
// previous digit
else {
for (int digit = prev + 1;
digit <= 9;
++digit) {
val += solve(i + 1, n,
digit, 1);
}
}
}
// Return the resultant total count
return val;
}
// Function to find all N-digit numbers
// satisfying the given criteria
static void countNdigitNumber(int N)
{
// Initialize an array []dp with
// all elements as -1
for(int i = 0;i<100;i++)
{
for (int j = 0; j < 10; j++) {
for (int k = 0; k < 2; k++)
dp[i,j,k] = -1;
}
}
// Function call to count all
// possible ways
Console.WriteLine(solve(0, N, 0, 0));
}
// Driver Code
public static void Main(String []args)
{
int N = 3;
countNdigitNumber(N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program for the above approach
// Declaration of dp table
var dp = Array(100).fill().map(()=>Array(10).fill().map(()=>Array(2).fill(-1)));
// Function to find the count of all N
// digit numbers such that all the digit
// is less than its adjacent digits
function solve(i , n , prev , sign) {
// Base Case:
// If i = n, then return 1 as valid
// number has been formed
if (i == n) {
return 1;
}
var val = dp[i][prev][sign];
// If the state has already been
// computed, then return it
if (val != -1)
return val;
// Stores the total count of ways
// for the current recursive call
val = 0;
// If i = 0, any digit from [1-9]
// can be placed and also if N = 1
// , then 0 can also be placed
if (i == 0) {
for (var digit = (n == 1 ? 0 : 1); digit <= 9; ++digit) {
val += solve(i + 1, n, digit, sign);
}
}
// If i = 1, any digit from [0-9]
// can be placed such that digit
// is not equal to previous digit
else if (i == 1) {
for (var digit = 0; digit <= 9; ++digit) {
// If the current digit is
// not same as the prev
if (digit != prev) {
val += solve(i + 1, n, digit, ((digit > prev) ? 1 : 0));
}
}
}
else {
// Place the current digit such
// that it is less than the
// previous digit
if (sign == 1) {
for (var digit = prev - 1; digit >= 0; --digit) {
val += solve(i + 1, n, digit, 0);
}
}
// Place current digit such
// that it is more than the
// previous digit
else {
for (var digit = prev + 1; digit <= 9; ++digit) {
val += solve(i + 1, n, digit, 1);
}
}
}
// Return the resultant total count
return val;
}
// Function to find all N-digit numbers
// satisfying the given criteria
function countNdigitNumber(N) {
// Function call to count all
// possible ways
document.write(solve(0, N, 0, 0));
}
// Driver Code
var N = 3;
countNdigitNumber(N);
// This code is contributed by gauravrajput1
</script>
Producción:
525
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA