Given an integer n > 0, which denotes the number of digits, the task to find total number of n-digit positive integers which are non-decreasing in nature.

A non-decreasing integer is a one in which all the digits from left to right are in non-decreasing form. ex: 1234, 1135, ..etc.

Note :Leading zeros also count in non-decreasing integers such as 0000, 0001, 0023, etc are also non-decreasing integers of 4-digits.

Examples:

Input : n = 1

Output : 10

Numbers are 0, 1, 2, ...9.

Input : n = 2

Output : 55

Input : n = 4

Output : 715

where n<10^3

Good day to you,

Imho some DP could be used for this purposes. The parameters might be [DigitsRemaining <=10^3][LastUsedDigit <10]. In body, we could simply try all digits betweer <LastUsedDigit,9>.

We call such DP with [n][0].

If they want the output "by modulo" then it shall be easy like this with complexity A(N*10*10). In other case some efficient BigInteger structure shall be used (but It might also pass, since there won't be more than 10^(10^3) numbers :P)

Good Luck & Have Nice Day!

can you explain more sir?

What part exactly?

It might look like following pseudocode: (+/-)

So some recursion on such base.

GL

I am unable to derive dp formula can you make that please?

Let's observe that the final number will have some digits 0 (possibly zero), some digits 1 (possibly zero), some digits 2 (possibly zero), etc.. In total, there will be

ndigits and they must be in non-decreasing order. For any combination of digits, there will be only one number that satisfies the non-decreasing condition, so let's see the problem in this way: We have 10 boxes and we have to distributenballs into them. This is a fairly known problem and the answer in this case is .