Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

Count of all n digit numbers with digits in non-decreasing order

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


Algorithm to find the count of all n digit numbers with digits in non-decreasing order


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


all n digit numbers with the digits in non-decreasing order


  • 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


Recommended Programs





If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in
Explore 'c plus plus'
Articles Practice Exercises