Dado un entero positivo N , la tarea es contar el número de números de N dígitos que tienen una diferencia absoluta entre dígitos consecutivos en orden no creciente.
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 = 3
Salida: 495
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 aquellos números cuyos dígitos están en orden no creciente. Después de verificar todos los números, imprima el valor de conteo como resultado.
Complejidad de Tiempo: 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ó, devuelve 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, itere a través de todos los números desde i = 0 hasta i = 9 , y compruebe si la condición (abs(prev1 – i) <= abs(prev1 – prev2)) es válida o no y, en consecuencia, coloque los valores ‘i’ satisfactorios en el posición actual.
- 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 count N-digit numbers
// having absolute difference between
// adjacent digits in non-increasing order
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 the current digit is 1,
// then any digit from [1-9]
// can be placed
if (digit == 1) {
for (int i = (n == 1 ? 0 : 1);
i <= 9; ++i) {
val += countOfNumbers(
digit + 1, i, prev1, n);
}
}
// If the current digit is 2, any
// digit from [0-9] can be placed
else if (digit == 2) {
for (int i = 0; i <= 9; ++i) {
val += countOfNumbers(
digit + 1, i, prev1, n);
}
}
// For other digits, any digit i
// can be placed which satisfies
// abs(prev1 - i) <= abs(prev1 - prev2)
else {
int diff = abs(prev2 - prev1);
for (int i = 0; i <= 9; ++i) {
// If absolute difference is
// less than or equal to diff
if (abs(prev1 - i) <= diff) {
val += countOfNumbers(
digit + 1, i,
prev1, n);
}
}
}
return val;
}
// Function to count N-digit numbers with
// absolute difference between adjacent
// digits in non increasing order
int countNumbersUtil(int N)
{
// Initialize dp table with -1
memset(dp, -1, sizeof dp);
// Function Call
cout << countOfNumbers(1, 0, 0, N);
}
// Driver code
int main()
{
int N = 3;
countNumbersUtil(N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
static int dp[][][] = new int[100][10][10];
// Function to count N-digit numbers
// having absolute difference between
// adjacent digits in non-increasing order
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 the current digit is 1,
// then any digit from [1-9]
// can be placed
if (digit == 1)
{
for(int i = (n == 1 ? 0 : 1);
i <= 9; ++i)
{
val += countOfNumbers(
digit + 1, i, prev1, n);
}
}
// If the current digit is 2, any
// digit from [0-9] can be placed
else if (digit == 2)
{
for(int i = 0; i <= 9; ++i)
{
val += countOfNumbers(
digit + 1, i, prev1, n);
}
}
// For other digits, any digit i
// can be placed which satisfies
// abs(prev1 - i) <= abs(prev1 - prev2)
else
{
int diff = Math.abs(prev2 - prev1);
for(int i = 0; i <= 9; ++i)
{
// If absolute difference is
// less than or equal to diff
if (Math.abs(prev1 - i) <= diff)
{
val += countOfNumbers(
digit + 1, i,
prev1, n);
}
}
}
return val;
}
// Function to count N-digit numbers with
// absolute difference between adjacent
// digits in non increasing order
static void countNumbersUtil(int N)
{
// Initialize dp table 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;
}
}
}
// Function Call
System.out.println(countOfNumbers(1, 0, 0, N));
}
// Driver code
public static void main(String[] args)
{
int N = 3;
countNumbersUtil(N);
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python3 program for the above approach dp = [[[0 for i in range(10)] for col in range(10)] for row in range(100)] # Function to count N-digit numbers # having absolute difference between # adjacent digits in non-increasing order 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 the current digit is 1, # then any digit from [1-9] # can be placed if (digit == 1): i = 1 if n == 1: i = 0 for j in range(i, 10): val += countOfNumbers(digit + 1, j, prev1, n) # If the current digit is 2, any # digit from [0-9] can be placed elif (digit == 2): for i in range(0, 10): val += countOfNumbers(digit + 1, i, prev1, n) # For other digits, any digit i # can be placed which satisfies # abs(prev1 - i) <= abs(prev1 - prev2) else: diff = abs(prev2 - prev1) for i in range(0, 10): # If absolute difference is # less than or equal to diff if (abs(prev1 - i) <= diff): val += countOfNumbers(digit + 1, i, prev1, n) return val # Function to count N-digit numbers with # absolute difference between adjacent # digits in non increasing order def countNumbersUtil(N): # Initialize dp table with -1 for i in range(0, 100): for j in range(0, 10): for k in range(0, 10): dp[i][j][k] = -1 # Function Call print(countOfNumbers(1, 0, 0, N)) # Driver code N = 3 countNumbersUtil(N) # This 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 count N-digit numbers
// having absolute difference between
// adjacent digits in non-increasing order
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 the current digit is 1,
// then any digit from [1-9]
// can be placed
if (digit == 1)
{
for(int i = (n == 1 ? 0 : 1);
i <= 9; ++i)
{
val += countOfNumbers(
digit + 1, i, prev1, n);
}
}
// If the current digit is 2, any
// digit from [0-9] can be placed
else if (digit == 2)
{
for(int i = 0; i <= 9; ++i)
{
val += countOfNumbers(
digit + 1, i, prev1, n);
}
}
// For other digits, any digit i
// can be placed which satisfies
// abs(prev1 - i) <= abs(prev1 - prev2)
else
{
int diff = Math.Abs(prev2 - prev1);
for(int i = 0; i <= 9; ++i)
{
// If absolute difference is
// less than or equal to diff
if (Math.Abs(prev1 - i) <= diff)
{
val += countOfNumbers(
digit + 1, i,
prev1, n);
}
}
}
return val;
}
// Function to count N-digit numbers with
// absolute difference between adjacent
// digits in non increasing order
static void countNumbersUtil(int N)
{
// Initialize dp table 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;
}
}
}
// Function Call
Console.WriteLine(countOfNumbers(1, 0, 0, N));
}
// Driver code
static public void Main()
{
int N = 3;
countNumbersUtil(N);
}
}
// This code is contributed by splevel62
Javascript
<script>
// javascript program for the above approach
var dp = Array(100).fill().map(() => Array(10).fill(0).map(()=>Array(10).fill(0)));
// Function to count N-digit numbers
// having absolute difference between
// adjacent digits in non-increasing order
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 the current digit is 1,
// then any digit from [1-9]
// can be placed
if (digit == 1) {
for (var i = (n == 1 ? 0 : 1); i <= 9; ++i) {
val += countOfNumbers(digit + 1, i, prev1, n);
}
}
// If the current digit is 2, any
// digit from [0-9] can be placed
else if (digit == 2) {
for (var i = 0; i <= 9; ++i) {
val += countOfNumbers(digit + 1, i, prev1, n);
}
}
// For other digits, any digit i
// can be placed which satisfies
// abs(prev1 - i) <= abs(prev1 - prev2)
else {
var diff = Math.abs(prev2 - prev1);
for (var i = 0; i <= 9; ++i) {
// If absolute difference is
// less than or equal to diff
if (Math.abs(prev1 - i) <= diff) {
val += countOfNumbers(digit + 1, i, prev1, n);
}
}
}
return val;
}
// Function to count N-digit numbers with
// absolute difference between adjacent
// digits in non increasing order
function countNumbersUtil(N) {
// Initialize dp table with -1
for (var i = 0; i < 100; i++) {
for (var j = 0; j < 10; j++) {
for (var k = 0; k < 10; k++) {
dp[i][j][k] = -1;
}
}
}
// Function Call
document.write(countOfNumbers(1, 0, 0, N));
}
// Driver code
var N = 3;
countNumbersUtil(N);
// This code is contributed by gauravrajput1
</script>
Producción
495
Complejidad de Tiempo: O(N * 10 3 )
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