Recuento de números de N dígitos estrictamente crecientes

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *