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=2Total 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.