Home » Interview coding problems/challenges

Total number of non-decreasing numbers with n digits

Here, we are going to see how many non-decreasing numbers can be generated of length n digits? Submitted by Radib Kar, on September 15, 2019

Problem statement

How many non-decreasing numbers can be generated of n digit length?

Example

Non-decreasing number means the digits from left to right will be in ascending order

    123 is non-decreasing
    213 is not
    Say
    n=1

    So non-decreasing numbers will be all the single digit numbers
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    
    Total number of non-decreasing numbers of 1 digit=10
    
    Now, if n=2
    Non-decreasing numbers will be
    00
    01
    02
    03
    04
    05
    06
    07
    08
    09
    11
    12
    13
    ..
    So on,
    Note: numbers with leading 0 is also counted

    10 is not included in the list
    
    For n=2
    Total number of non-decreasing numbers is 55
    (List all yourself if you have doubt!)

Solution

We will solve this problem with the help of combinatorics

Let's first see, how we can build up the generating function.

When n=1
We have 10 non-decreasing numbers(0-9)
    
Now, for n=2
Numbers starting with 0 is
00
01
02
...
09
count is 10
Numbers starting with 1 is
11
12
13
...
19
Count is 9(as 10 not allowed)
    
Similarly, 
count numbers starting with 2 is 8 (20, 21 not allowed)
count numbers starting with 3 is 7 (30, 31, 32 not allowed)
count numbers starting with 4 is 6 (40, 41, 42, 43 not allowed)
count numbers starting with 5 is 5(50, 51, 52, 53, 54 not allowed)
count numbers starting with 6 is 4(60, 61, 62, 63, 64, 65 not allowed)
count numbers starting with 7 is 3(70, 71, 72, 73, 74, 75, 76 not allowed)
count numbers starting with 8 is 2(80, 81, 82, 83, 84, 85, 86, 87 not allowed)
count numbers starting with 9 is 1(90, 91, 92, 93, 94, 95, 96, 97, 98 not allowed)

Total count of non-decreasing numbers with 2-digit
10+9+8+7+6+5+4+3+2+1
=1+2+3+4+5+6+7+8+9+10
=10 *(10 +1)/2


Now this is the total number of non-decreasing 2 digit number
Now we can add a 0 to the left of all this numbers to make it 3 digit
Ex: 000
    001
    So on
    
Still all will be valid 3 digit non-decreasing  as 0 is smallest
So count of 3-digit number starting with 0 is 10*(10+1)/2 
Now we can add a 1 to the left of all this numbers to make it 3 digit
But in that case we can't add 1 to 2-digit number starting with 0
Like 100
101
...

These are not part of list
That's why count of 3-digit non-decreasing number starting with 1
=   All 3-digit no starting with 1 (which is same as all the 3-digit no 
    starting with 0) - All 2-digit no starting with 0
=10*(10+1)/2- 10
=10*(10-1)/2
Similarly,
count of the 3-digit non-decreasing number starting with 2

=   All 3-digit no starting with 2 (which is same as all the 3-digit no 
    starting with 0 or starting with 1)
    - (All 2-digit no starting with 0+ All 2-digit no starting with 1)
=10*(10+1)/2- 2*10
=10*(10-1)/2-10
=10*(10-1)/2 -5 -5
= (10-1)*(10-2)/2

In this way,
count of the 3-digit non-decreasing number starting with 3
= 10*(10+1)/2- 3*10
= (10-2)*(10-3)/2

count of the 3-digit non-decreasing number starting with 4
= 10*(10+1)/2- 4*10
= (10-3) * (10-4)/2

count of the 3-digit non-decreasing number starting with 5
= 10*(10+1)/2- 5*10
= (10-4) * (10-5)/2

count of the 3-digit non-decreasing number starting with 6
= 10*(10+1)/2- 6*10
= (10-5) * (10-6)/2

count of the 3-digit non-decreasing number starting with 7
= 10*(10+1)/2- 7*10
= (10-6) * (10-7)/2

count of the 3-digit non-decreasing number starting with 8
= 10*(10+1)/2- 8*10
= (10-7) * (10-8)/2
= 3

count of the 3-digit non-decreasing number starting with 9
= 10*(10+1)/2- 9*10
= (10-8) * (10-9)/2
= 1

Total 3 digit non-decreasing numbers will be summation of all of above,
=   10*(10+1)/2 +(10-1)*(10)/2 + (10-2)*(10-1)/2 + (10-3)*(10-2)/2+ (10-4)*(10-3)/2+ 
    (10-5)*(10-4)/2+ (10-6)*(10-5)/2+ (10-7)*(10-6)/2+ 3+ 1

Take in group of two to add
Like
First two,
10*(10+1)/2 +(10-1)*(10)/2
=10/2*(10+1+10-1)/2=(10^2)/2

Next two,
(10-2)*(10-1)/2 +(10-3)*(10-2)/2
=(10-2)/2*(10-2)=((10-2)^2)/2

Next two,
(10-4)*(10-3)/2 +(10-5)*(10-4)/2
=(10-4)/2*(10-4)=((10-4)^2)/2

Next two,
If you compute,
=((10-6)^2)/2

Last two
4
If we add these five
=(10^2+(10-2)^2+(10-4)^2+(10-6)^2+4)/2
=½ *(2^2+4^2+6^2+8^2+10^2) (sum of even square series up to 10)
=10*(10+1)/2*(10+2)/3 (total count of three digit non-decreasing number)

Now, come to generalization for n digits,
So for one digit =10
Two digit=10*(10+1)/2
Three digit=10*(10+1)/2*(10+2)/3

By induction we can prove from these,
For n digit,
10*(10+1)/2*(10+2)/3*…*(10+n-1)/n

//Code snippet two compute the above formula,
count=1
For  i=1:n
        count=(count*(10+i-1))/ I

C++ Implementation

#include <iostream>
using namespace std;

int main()
{
	int n;
	
	cout<<"Enter value of n(total n of digit)\n";	
	cin>>n;
	
	long long int count=1;

	//code to calculate the formula
	for(int i=1;i<=n;i++){

		count=(count*(10+i-1))/i;
	}
	cout<<"Number of non-decreasing numbers with n digit: "<<count<<endl;
	
	return 0;
}

Output

RUN 1:
Enter value of n(total n of digit)
3
Number of non-decreasing numbers with n digit: 220

RUN 2:
Enter value of n(total n of digit)
4
Number of non-decreasing numbers with n digit: 715