Dado n, encuentre el conteo de n dígitos Números escalonados . Un número se llama número de paso si todos los dígitos adyacentes tienen una diferencia absoluta de 1. 321 es un número de paso mientras que 421 no lo es.
Ejemplos:
Input : 2 Output : 17 Explanation: The numbers are 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98. Input : 1 Output : 10 Explanation: the numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
Un enfoque ingenuo es ejecutar un ciclo para todos los números de n dígitos y verificar cada número si está escalonado.
Un enfoque eficiente es utilizar la programación dinámica .
In dp[i][j], i denotes number of
digits and j denotes last digit.
// If there is only one digit
if (i == 1)
dp(i, j) = 1;
// If last digit is 0.
if (j == 0)
dp(i, j) = dp(i-1, j+1)
// If last digit is 9
else if (j == 9)
dp(i, j) = dp(i-1, j-1)
// If last digit is neither 0
// nor 9.
else
dp(i, j) = dp(i-1, j-1) +
dp(i-1, j+1)
Result is ∑dp(n, j) where j varies
from 1 to 9.
C++
// CPP program to calculate the number of
// n digit stepping numbers.
#include <bits/stdc++.h>
using namespace std;
// function that calculates the answer
long long answer(int n)
{
// dp[i][j] stores count of i digit
// stepping numbers ending with digit
// j.
int dp[n + 1][10];
// if n is 1 then answer will be 10.
if (n == 1)
return 10;
// Initialize values for count of
// digits equal to 1.
for (int j = 0; j <= 9; j++)
dp[1][j] = 1;
// Compute values for count of digits
// more than 1.
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= 9; j++) {
// If ending digit is 0
if (j == 0)
dp[i][j] = dp[i - 1][j + 1];
// If ending digit is 9
else if (j == 9)
dp[i][j] = dp[i - 1][j - 1];
// For other digits.
else
dp[i][j] = dp[i - 1][j - 1] +
dp[i - 1][j + 1];
}
}
// stores the final answer
long long sum = 0;
for (int j = 1; j <= 9; j++)
sum += dp[n][j];
return sum;
}
// driver program to test the above function
int main()
{
int n = 2;
cout << answer(n);
return 0;
}
Java
// Java program to calculate the number of
// n digit stepping numbers.
class GFG {
// function that calculates the answer
static long answer(int n)
{
// dp[i][j] stores count of i
// digit stepping numbers ending
// with digit j.
int dp[][] = new int[n+1][10];
// if n is 1 then answer will be 10.
if (n == 1)
return 10;
// Initialize values for count of
// digits equal to 1.
for (int j = 0; j <= 9; j++)
dp[1][j] = 1;
// Compute values for count of
// digits more than 1.
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= 9; j++) {
// If ending digit is 0
if (j == 0)
dp[i][j] = dp[i - 1][j + 1];
// If ending digit is 9
else if (j == 9)
dp[i][j] = dp[i - 1][j - 1];
// For other digits.
else
dp[i][j] = dp[i - 1][j - 1] +
dp[i - 1][j + 1];
}
}
// stores the final answer
long sum = 0;
for (int j = 1; j <= 9; j++)
sum += dp[n][j];
return sum;
}
// driver program to test the above function
public static void main(String args[])
{
int n = 2;
System.out.println(answer(n));
}
}
/*This code is contributed by Nikita tiwari.*/
Python3
# Python3 program to calculate # the number of n digit # stepping numbers. # function that calculates # the answer def answer(n): # dp[i][j] stores count of # i digit stepping numbers # ending with digit j. dp = [[0 for x in range(10)] for y in range(n + 1)]; # if n is 1 then answer # will be 10. if (n == 1): return 10; for j in range(10): dp[1][j] = 1; # Compute values for count # of digits more than 1. for i in range(2, n + 1): for j in range(10): # If ending digit is 0 if (j == 0): dp[i][j] = dp[i - 1][j + 1]; # If ending digit is 9 elif (j == 9): dp[i][j] = dp[i - 1][j - 1]; # For other digits. else: dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]); # stores the final answer sum = 0; for j in range(1, 10): sum = sum + dp[n][j]; return sum; # Driver Code n = 2; print(answer(n)); # This code is contributed # by mits
C#
// C# program to calculate the number of
// n digit stepping numbers.
using System;
class GFG {
// function that calculates the answer
static long answer(int n)
{
// dp[i][j] stores count of i
// digit stepping numbers ending
// with digit j.
int [,]dp = new int[n+1,10];
// if n is 1 then answer will be 10.
if (n == 1)
return 10;
// Initialize values for count of
// digits equal to 1.
for (int j = 0; j <= 9; j++)
dp[1,j] = 1;
// Compute values for count of
// digits more than 1.
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= 9; j++) {
// If ending digit is 0
if (j == 0)
dp[i,j] = dp[i - 1,j + 1];
// If ending digit is 9
else if (j == 9)
dp[i,j] = dp[i - 1,j - 1];
// For other digits.
else
dp[i,j] = dp[i - 1,j - 1] +
dp[i - 1,j + 1];
}
}
// stores the final answer
long sum = 0;
for (int j = 1; j <= 9; j++)
sum += dp[n,j];
return sum;
}
// driver program to test the above function
public static void Main()
{
int n = 2;
Console.WriteLine(answer(n));
}
}
/*This code is contributed by vt_m.*/
PHP
<?php
// PHP program to calculate
// the number of n digit
// stepping numbers.
// function that calculates
// the answer
function answer($n)
{
// dp[i][j] stores count of
// i digit stepping numbers
// ending with digit j.
// if n is 1 then answer
// will be 10.
if ($n == 1)
return 10;
for ( $j = 0; $j <= 9; $j++)
$dp[1][$j] = 1;
// Compute values for count
// of digits more than 1.
for ($i = 2; $i <= $n; $i++)
{
for ($j = 0; $j <= 9; $j++)
{
// If ending digit is 0
if ($j == 0)
$dp[$i][$j] = $dp[$i - 1][$j + 1];
// If ending digit is 9
else if ($j == 9)
$dp[$i][$j] = $dp[$i - 1][$j - 1];
// For other digits.
else
$dp[$i][$j] = $dp[$i - 1][$j - 1] +
$dp[$i - 1][$j + 1];
}
}
// stores the final answer
$sum = 0;
for ($j = 1; $j <= 9; $j++)
$sum += $dp[$n][$j];
return $sum;
}
// Driver Code
$n = 2;
echo answer($n);
// This code is contributed by aj_36
?>
Javascript
<script>
// JavaScript program to calculate the number of
// n digit stepping numbers.
// Function that calculates the answer
function answer(n)
{
// dp[i][j] stores count of i
// digit stepping numbers ending
// with digit j.
let dp = new Array(n + 1);
// Loop to create 2D array using 1D array
for(var i = 0; i < dp.length; i++)
{
dp[i] = new Array(2);
}
// If n is 1 then answer will be 10.
if (n == 1)
return 10;
// Initialize values for count of
// digits equal to 1.
for(let j = 0; j <= 9; j++)
dp[1][j] = 1;
// Compute values for count of
// digits more than 1.
for(let i = 2; i <= n; i++)
{
for(let j = 0; j <= 9; j++)
{
// If ending digit is 0
if (j == 0)
dp[i][j] = dp[i - 1][j + 1];
// If ending digit is 9
else if (j == 9)
dp[i][j] = dp[i - 1][j - 1];
// For other digits.
else
dp[i][j] = dp[i - 1][j - 1] +
dp[i - 1][j + 1];
}
}
// Stores the final answer
let sum = 0;
for(let j = 1; j <= 9; j++)
sum += dp[n][j];
return sum;
}
// Driver Code
let n = 2;
document.write(answer(n));
// This code is contributed by code_hunt
</script>
Producción :
17
Complejidad de tiempo : O (n), ya que estamos usando un ciclo para atravesar n veces y dentro de cada iteración hay 10 casos. Entonces un total de 10*N que es equivalente a n .
Espacio auxiliar : O (n), ya que estamos usando un espacio adicional de 10 * n para la array dp.
Número de números escalonados de n dígitos | Solución optimizada para el espacio