A number is non-decreasing if every digit (except the first one) is greater than or equal to the previous digit. For example, 223, 4455567, 899, are non-decreasing numbers.
So, given the number of digits n, you are required to find the count of total non-decreasing numbers with n digits.
Examples:
Input: n = 1 Output: count = 10 Input: n = 2 Output: count = 55 Input: n = 3 Output: count = 220
Method 1: One way to look at the problem is, count of numbers is equal to count n digit number ending with 9 plus count of ending with digit 8 plus count for 7 and so on. How to get count ending with a particular digit? We can recur for n-1 length and digits smaller than or equal to the last digit. So below is recursive formula.
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)
Let count ending with digit ‘d’ and length n be count(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
The above recursive solution is going to have many overlapping subproblems. Therefore, we can use Dynamic Programming to build a table in bottom-up manner.
Below is the implementation of the above idea :
C++14
// 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
import java.io.*;
public 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>
Output
220
Thanks to Gaurav Ahirwar for suggesting above method.
Method 2: Another method is based on below direct formula
Count of non-decreasing numbers with n digits =
N*(N+1)/2*(N+2)/3* ....*(N+n-1)/n
Where N = 10
Below is the program to compute count using above formula.
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
import java.io.*;
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>
Output
220
Time Complexity: O(n)
Auxiliary Space: O(n)
Thanks to Abhishek Somani for suggesting this method.
How does this formula work?
N * (N+1)/2 * (N+2)/3 * .... * (N+n-1)/n Where N = 10
Let us try for different values of 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]
For general n digit case, we can apply Mathematical Induction. The count would be equal to count n-1 digit beginning with 0, i.e., N*(N+1)/2*(N+2)/3* ….*(N+n-1-1)/(n-1). Plus count of n-1 digit numbers beginning with 1, i.e., (N-1)*(N)/2*(N+1)/3* ….*(N-1+n-1-1)/(n-1) (Note that N is replaced by N-1) and so on.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
