Un número no es decreciente si todos sus dígitos (excepto el primero) son mayores o iguales que el dígito anterior. Por ejemplo, 223, 4455567, 899 son números no decrecientes.
Por lo tanto, dado el número de dígitos n, debe encontrar el recuento de números totales no decrecientes con n dígitos.
Ejemplos:
Input: n = 1 Output: count = 10 Input: n = 2 Output: count = 55 Input: n = 3 Output: count = 220
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Una forma de ver el problema es que el conteo de números es igual al conteo de n dígitos que terminan en 9 más el conteo de dígitos que terminan en 8 más el conteo de 7 y así sucesivamente. ¿Cómo hacer que el conteo termine con un dígito en particular? Podemos recurrir para longitudes n-1 y dígitos menores o iguales que el último dígito. Así que a continuación está la fórmula recursiva.
Count of n digit numbers = (Count of (n-1) digit numbers Ending with digit 9) +
(Count of (n-1) digit numbers Ending with digit 8) +
.............................................+
.............................................+
(Count of (n-1) digit numbers Ending with digit 0)
Sea el conteo que termina con el dígito ‘d’ y la longitud n (n, d)
count(n, d) = ∑(count(n-1, i)) where i varies from 0 to d Total count = ∑count(n-1, d) where d varies from 0 to n-1
La solución recursiva anterior tendrá muchos subproblemas superpuestos. Por lo tanto, podemos usar la programación dinámica para construir una tabla de forma ascendente.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to count non-decreasing number with n digits
#include<bits/stdc++.h>
using namespace std;
long long int countNonDecreasing(int n)
{
// dp[i][j] contains total count of non decreasing
// numbers ending with digit i and of length j
long long int dp[10][n+1];
memset(dp, 0, sizeof dp);
// Fill table for non decreasing numbers of length 1
// Base cases 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
for (int i = 0; i < 10; i++)
dp[i][1] = 1;
// Fill the table in bottom-up manner
for (int digit = 0; digit <= 9; digit++)
{
// Compute total numbers of non decreasing
// numbers of length 'len'
for (int len = 2; len <= n; len++)
{
// sum of all numbers of length of len-1
// in which last digit x is <= 'digit'
for (int x = 0; x <= digit; x++)
dp[digit][len] += dp[x][len-1];
}
}
long long int count = 0;
// There total nondecreasing numbers of length n
// won't be dp[0][n] + dp[1][n] ..+ dp[9][n]
for (int i = 0; i < 10; i++)
count += dp[i][n];
return count;
}
// Driver program
int main()
{
int n = 3;
cout << countNonDecreasing(n);
return 0;
}
Java
class NDN
{
static int countNonDecreasing(int n)
{
// dp[i][j] contains total count of non decreasing
// numbers ending with digit i and of length j
int dp[][] = new int[10][n+1];
// Fill table for non decreasing numbers of length 1
// Base cases 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
for (int i = 0; i < 10; i++)
dp[i][1] = 1;
// Fill the table in bottom-up manner
for (int digit = 0; digit <= 9; digit++)
{
// Compute total numbers of non decreasing
// numbers of length 'len'
for (int len = 2; len <= n; len++)
{
// sum of all numbers of length of len-1
// in which last digit x is <= 'digit'
for (int x = 0; x <= digit; x++)
dp[digit][len] += dp[x][len-1];
}
}
int count = 0;
// There total nondecreasing numbers of length n
// won't be dp[0][n] + dp[1][n] ..+ dp[9][n]
for (int i = 0; i < 10; i++)
count += dp[i][n];
return count;
}
public static void main(String args[])
{
int n = 3;
System.out.println(countNonDecreasing(n));
}
}/* This code is contributed by Rajat Mishra */
Python3
# Python3 program to count # non-decreasing number with n digits def countNonDecreasing(n): # dp[i][j] contains total count # of non decreasing numbers ending # with digit i and of length j dp = [[0 for i in range(n + 1)] for i in range(10)] # Fill table for non decreasing # numbers of length 1. # Base cases 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 for i in range(10): dp[i][1] = 1 # Fill the table in bottom-up manner for digit in range(10): # Compute total numbers of non # decreasing numbers of length 'len' for len in range(2, n + 1): # sum of all numbers of length # of len-1 in which last # digit x is <= 'digit' for x in range(digit + 1): dp[digit][len] += dp[x][len - 1] count = 0 # There total nondecreasing numbers # of length n won't be dp[0][n] + # dp[1][n] ..+ dp[9][n] for i in range(10): count += dp[i][n] return count # Driver Code n = 3 print(countNonDecreasing(n)) # This code is contributed # by sahilshelangia
C#
// C# program to print sum
// triangle for a given array
using System;
class GFG {
static int countNonDecreasing(int n)
{
// dp[i][j] contains total count
// of non decreasing numbers ending
// with digit i and of length j
int [,]dp = new int[10,n + 1];
// Fill table for non decreasing
// numbers of length 1 Base cases
// 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
for (int i = 0; i < 10; i++)
dp[i, 1] = 1;
// Fill the table in bottom-up manner
for (int digit = 0; digit <= 9; digit++)
{
// Compute total numbers of non decreasing
// numbers of length 'len'
for (int len = 2; len <= n; len++)
{
// sum of all numbers of length of len-1
// in which last digit x is <= 'digit'
for (int x = 0; x <= digit; x++)
dp[digit, len] += dp[x, len - 1];
}
}
int count = 0;
// There total nondecreasing numbers
// of length n won't be dp[0][n]
// + dp[1][n] ..+ dp[9][n]
for (int i = 0; i < 10; i++)
count += dp[i, n];
return count;
}
// Driver code
public static void Main()
{
int n = 3;
Console.WriteLine(countNonDecreasing(n));
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP program to count non-decreasing number with n digits
function countNonDecreasing($n)
{
// dp[i][j] contains total count of non decreasing
// numbers ending with digit i and of length j
$dp = array_fill(0,10,array_fill(0,$n+1,NULL));
// Fill table for non decreasing numbers of length 1
// Base cases 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
for ($i = 0; $i < 10; $i++)
$dp[$i][1] = 1;
// Fill the table in bottom-up manner
for ($digit = 0; $digit <= 9; $digit++)
{
// Compute total numbers of non decreasing
// numbers of length 'len'
for ($len = 2; $len <= $n; $len++)
{
// sum of all numbers of length of len-1
// in which last digit x is <= 'digit'
for ($x = 0; $x <= $digit; $x++)
$dp[$digit][$len] += $dp[$x][$len-1];
}
}
$count = 0;
// There total nondecreasing numbers of length n
// won't be dp[0][n] + dp[1][n] ..+ dp[9][n]
for ($i = 0; $i < 10; $i++)
$count += $dp[$i][$n];
return $count;
}
// Driver program
$n = 3;
echo countNonDecreasing($n);
return 0;
?>
Javascript
<script>
function countNonDecreasing(n)
{
// dp[i][j] contains total count of non decreasing
// numbers ending with digit i and of length j
let dp=new Array(10);
for(let i=0;i<10;i++)
{
dp[i]=new Array(n+1);
}
for(let i=0;i<10;i++)
{
for(let j=0;j<n+1;j++)
{
dp[i][j]=0;
}
}
// Fill table for non decreasing numbers of length 1
// Base cases 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
for (let i = 0; i < 10; i++)
dp[i][1] = 1;
// Fill the table in bottom-up manner
for (let digit = 0; digit <= 9; digit++)
{
// Compute total numbers of non decreasing
// numbers of length 'len'
for (let len = 2; len <= n; len++)
{
// sum of all numbers of length of len-1
// in which last digit x is <= 'digit'
for (let x = 0; x <= digit; x++)
dp[digit][len] += dp[x][len-1];
}
}
let count = 0;
// There total nondecreasing numbers of length n
// won't be dp[0][n] + dp[1][n] ..+ dp[9][n]
for (let i = 0; i < 10; i++)
count += dp[i][n];
return count;
}
let n = 3;
document.write(countNonDecreasing(n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
220
Gracias a Gaurav Ahirwar por sugerir el método anterior.
Otro método se basa en la siguiente fórmula directa
Count of non-decreasing numbers with n digits =
N*(N+1)/2*(N+2)/3* ....*(N+n-1)/n
Where N = 10
A continuación se muestra el programa para calcular el conteo usando la fórmula anterior.
C++
// C++ program to count non-decreasing number with n digits
#include<bits/stdc++.h>
using namespace std;
long long int countNonDecreasing(int n)
{
int N = 10;
// Compute value of N*(N+1)/2*(N+2)/3* ....*(N+n-1)/n
long long count = 1;
for (int i=1; i<=n; i++)
{
count *= (N+i-1);
count /= i;
}
return count;
}
// Driver program
int main()
{
int n = 3;
cout << countNonDecreasing(n);
return 0;
}
Java
// java program to count non-decreasing
// number with n digits
public class GFG {
static long countNonDecreasing(int n)
{
int N = 10;
// Compute value of N * (N+1)/2 *
// (N+2)/3 * ....* (N+n-1)/n
long count = 1;
for (int i = 1; i <= n; i++)
{
count *= (N + i - 1);
count /= i;
}
return count;
}
// Driver code
public static void main(String args[]) {
int n = 3;
System.out.print(countNonDecreasing(n));
}
}
// This code is contributed by Sam007.
Python3
# python program to count non-decreasing # number with n digits def countNonDecreasing(n): N = 10 # Compute value of N*(N+1)/2*(N+2)/3 # * ....*(N+n-1)/n count = 1 for i in range(1, n+1): count = int(count * (N+i-1)) count = int(count / i ) return count # Driver program n = 3; print(countNonDecreasing(n)) # This code is contributed by Sam007
C#
// C# program to count non-decreasing
// number with n digits
using System;
class GFG {
static long countNonDecreasing(int n)
{
int N = 10;
// Compute value of N * (N+1)/2 *
// (N+2)/3 * ....* (N+n-1)/n
long count = 1;
for (int i = 1; i <= n; i++)
{
count *= (N + i - 1);
count /= i;
}
return count;
}
public static void Main()
{
int n = 3;
Console.WriteLine(countNonDecreasing(n));
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP program to count non-decreasing
// number with n digits
function countNonDecreasing($n)
{
$N = 10;
// Compute value of N*(N+1)/2*(N+2)/3* ...
// ....*(N+n-1)/n
$count = 1;
for ($i = 1; $i <= $n; $i++)
{
$count *= ($N + $i - 1);
$count /= $i;
}
return $count;
}
// Driver Code
$n = 3;
echo countNonDecreasing($n);
// This code is contributed by Sam007
?>
Javascript
<script>
// javascript program to count non-decreasing
// number with n digits
function countNonDecreasing(n)
{
let N = 10;
// Compute value of N * (N+1)/2 *
// (N+2)/3 * ....* (N+n-1)/n
let count = 1;
for (let i = 1; i <= n; i++)
{
count *= (N + i - 1);
count = Math.floor(count/ i);
}
return count;
}
// Driver code
let n = 3;
document.write(countNonDecreasing(n));
// This code is contributed by rag2127.
</script>
Producción:
220
Gracias a Abhishek Somani por sugerir este método.
¿Cómo funciona esta fórmula?
N * (N+1)/2 * (N+2)/3 * .... * (N+n-1)/n Where N = 10
Probemos con diferentes valores de n.
For n = 1, the value is N from formula.
Which is true as for n = 1, we have all single digit
numbers, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
For n = 2, the value is N(N+1)/2 from formula
We can have N numbers beginning with 0, (N-1) numbers
beginning with 1, and so on.
So sum is N + (N-1) + .... + 1 = N(N+1)/2
For n = 3, the value is N(N+1)/2(N+2)/3 from formula
We can have N(N+1)/2 numbers beginning with 0, (N-1)N/2
numbers beginning with 1 (Note that when we begin with 1,
we have N-1 digits left to consider for remaining places),
(N-2)(N-1)/2 beginning with 2, and so on.
Count = N(N+1)/2 + (N-1)N/2 + (N-2)(N-1)/2 +
(N-3)(N-2)/2 .... 3 + 1
[Combining first 2 terms, next 2 terms and so on]
= 1/2[N2 + (N-2)2 + .... 4]
= N*(N+1)*(N+2)/6 [Refer this , putting n=N/2 in the
even sum formula]
Para el caso general de n dígitos, podemos aplicar la inducción matemática. La cuenta sería igual a contar n-1 dígito comenzando con 0, es decir, N*(N+1)/2*(N+2)/3* ….*(N+n-1-1)/(n -1). Más recuento de números de n-1 dígito que comienzan con 1, es decir, (N-1)*(N)/2*(N+1)/3* ….*(N-1+n-1-1)/( n-1) (Tenga en cuenta que N se reemplaza por N-1) y así sucesivamente.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA