Total number of non-decreasing numbers with n digits
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> |
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> |
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.
Contact Us