Count of all n digit numbers with digits in non-decreasing order

A non-decreasing number is a number whose digits are in non-decreasing order such as 11 12 22 34 33 etc., Given a number n which is the length of the number, print the count of all n digit numbers with the digits in non-decreasing order.

For example, 

Input: n = 1

Output: count = 10

Explanation:  The  numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Input: n = 5

Output: count = 2002

Algorithm to find the count of all n digit numbers with digits in non-decreasing order

  • One way to investigate the problem is to have the number of numbers equal to the number of n-digit numbers ending with 9 plus the number with the number 8 and the number for 7, and so on.
  • To get the count with a specific number return for n-1 length and digits less than or equal to the last digit. Below is the recursive formula of the approach,

all n digit numbers with the digits in non-decreasing order

  • The above recursive solution contains overlapping subproblems increasing the time complexity.
  • Therefore, use Dynamic Programming approach to build a table in a bottom-up manner.
  • The solution using Dynamic Programming is given below.

/* C++ program to find the count of all n digit numbers with the digits in non-decreasing order */

#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
long long int dp[10][n+1]; 
for(int i=0;i<10;i++)
   for(int j=0;j<n+1;j++)
       dp[i][j]=0;
for(int i=0;i<10;i++)
   dp[i][1]=1;
for(int i=0;i<10;i++)
{
   for(int j=2;j<=n;j++)
   {
       for(int k=0;k<=i;k++)
       {
           dp[i][j]+=dp[k][j-1];
       }
   }
}
long long int count=0;
for(int i=0;i<10;i++)
   count+=dp[i][n];   // Update the count for the n value specified
cout<<count;
return 0;
}

Test Case 1
I/P
5
O/P
2002

Test Case 2
I/P
10
O/P
92378

Test Case 3
I/P
25
O/P
52451256

Test Case 4
I/P
4
O/P
715

Test Case 5
I/P
1
O/P
10