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

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

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.

Count of all n digits numbers with 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


face prep pro ad banner

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,
  • The above recursive solution contains overlapping subproblems increasing the time complexity.
  • Therefore, use the Dynamic Programming approach to build a table in a bottom-up manner.

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


face prep pro ad bannerClick here to learn more about FACE Prep PRO


The solution using Dynamic Programming is given below.

@@coding::1@@

Recommended Programs


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

c