Link copied to clipboard. Share away!

Dismiss

Published on 11 Mar 2020

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

- 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,

- 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++

Output

Input -
5
Output -
2002

**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

If you have any feedback about this
article and want to improve this, please write to **enquiry@faceprep.in**

×