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