Home » Interview coding problems/challenges

# Total number of non-decreasing numbers with n digits using dynamic programming

**Total number of non-decreasing numbers with n digits**: This is a standard interview problem based on recursion which can be featured in any company interview rounds.

Submitted by Radib Kar, on June 10, 2020

**Problem statement:**

Given the number of digits * n*, find the count of total non-decreasing numbers with

**digits.**

*n*A number is non-decreasing if every digit (except the first one) is greater than or equal to the previous digit. For example, 22,223, 45567, 899, are non-decreasing numbers whereas 321 or 322 are not.

**Input:**

The first line of input contains an integer * T* denoting the number of test cases. Then

*test cases follow. The first line of each test case contains the integer*

**T***.*

**n****Output:**

Print the count of total non-decreasing numbers with n digits for each test case in a new line. You may need to use unsigned long long int as the count can be very large.

**Constraints:**

1 <= T <= 100 1 <= n <= 200

**Example:**

Input: No of test cases, 3 n=1 n=2 n=3 Output: For n=1 Total count is: 10 For n=2 Total count is: 55 For n=3 Total count is: 220

**Explanation:**

For n=1, The non-decreasing numbers are basically 0 to 9, counting up to 10 For, n=2, The non-decreasing numbers can be 00 01 02 .. 11 12 13 14 15 .. so on total 55

**Solution Approach:**

The solution can be recursive. In recursion our strategy will be to build the string (read: number) such that at each recursive call the number to be appended would be necessarily bigger (or equal) than(to) the last one.

Say, at any recursion call,

The number already constructed is *x _{1}x_{2}...x_{i}* where

*i<n*, So at the recursive call we are allowed to append digits only which are equal to greater to

*x*.

_{i}So, let's formulate the recursion

Say, the recursive function is *computerecur(int index, int last, int n)*

Where,

*index*= current position to append digit*Last*= the previous digit*n*= number of total digits

unsigned long long int computerecur (int index,int last,int n){ // base case if(index has reached the last digit) return 1; unsigned long long int sum=0; for digit to append at current index,i=0 to 9 if(i>=last) // recur if I can be appended sum + =computerecur(index+1,i,n); end for return sum End function

So the basic idea to the recursion is that if it's a valid digit to append (depending on the last digit) then append it and recur for the remaining digits.

Now the call from the *main()* function should be done by appending the first digit already (basically we will keep that first digit as last digit position for the recursion call).

So at main,

We will call as,

unsigned long long int result=0; for i=0 to 9 //starting digits // index=0, starting digit assigned as // last digit for recursion result+=computerecur(0,i,n); end for

The result is the ultimate result.

I would suggest you draw the recursion tree to have a better understanding, Take *n=3* and do yourself.

For, *n=2*, I will brief the tree below

For starting digit 0 Computerecur(0,0,2) Index!=n-1 So Goes to the loop And then It calls to Computerecur(1,0,2) // it's for number 00 Computerecur(1,1,2) // it's for number 01 Computerecur(1,2,2) // it's for number 02 Computerecur(1,3,2) // it's for number 03 Computerecur(1,4,2) // it's for number 04 Computerecur(1,5,2) // it's for number 05 Computerecur(1,6,2) // it's for number 06 Computerecur(1,7,2) // it's for number 07 Computerecur(1,8,2) // it's for number 08 Computerecur(1,9,2) // it's for number 09 So on ...

Now, it's pretty easy to infer that it leads to many overlapping sub-problem and hence we need dynamic programming to store the results of overlapping sub-problems. That's why I have used the memoization technique to store the already computed sub-problem results. See the below implementation to understand the memorization part.

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; unsigned long long int dp[501][10]; unsigned long long int my(int index, int last, int n) { if (index == n - 1) return 1; // memorization, don't compute again what is already computed if (dp[index][last] != -1) return dp[index][last]; unsigned long long int sum = 0; for (int i = 0; i <= 9; i++) { if (i >= last) sum += my(index + 1, i, n); } dp[index][last] = sum; return dp[index][last]; } unsigned long long int compute(int n) { unsigned long long int sum = 0; for (int i = 0; i <= 9; i++) { sum += my(0, i, n); } return sum; } int main() { int t, n, item; cout << "enter number of testcase\n"; scanf("%d", &t); for (int i = 0; i < t; i++) { cout << "Enter the number of digits,n:\n"; scanf("%d", &n); for (int i = 0; i <= n; i++) { for (int j = 0; j <= 9; j++) { dp[i][j] = -1; } } cout << "number of non-decreasing number with " << n; cout << " digits are: " << compute(n) << endl; } return 0; }

**Output:**

enter number of testcase 3 Enter the number of digits,n: 2 number of non-decreasing number with 2 digits are: 55 Enter the number of digits,n: 3 number of non-decreasing number with 3 digits are: 220 Enter the number of digits,n: 6 number of non-decreasing number with 6 digits are: 5005

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.