How should I practice Count Nondecreasing Digit-Sum Arrays?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft online assessment problems in FastPrep.

Is Count Nondecreasing Digit-Sum Arrays associated with Microsoft?

FastPrep tags this as a Microsoft online assessment coding practice problem when the problem catalog has that company and stage context.

Count Nondecreasing Digit-Sum Arrays

Microsoft● HardFULLTIMEOA

Learn

Problem statement

Given an integer array requiredSum of length n, count the arrays result of length n that satisfy all of the following rules:

result is nondecreasing, so result[i] <= result[i + 1] for every valid i.
For every index i, the sum of the decimal digits of result[i] equals requiredSum[i].
Every value in result is between 1 and 5000, inclusive.

Return the number of distinct valid arrays modulo 10^9 + 7.

Function

countDigitSumArrays(requiredSum: int[]) → int

Examples

Example 1

requiredSum = [1]return = 4

The valid one-element arrays are [1], [10], [100], and [1000].

Example 2

requiredSum = [1,1]return = 10

The only eligible values are 1, 10, 100, and 1000. Choosing any two of them with repetition and writing them in nondecreasing order gives 10 arrays.

Example 3

requiredSum = [31,1]return = 0

The only value at most 5000 with digit sum 31 is 4999. No value greater than or equal to 4999 has digit sum 1, so no valid nondecreasing array exists.

Constraints

1 <= requiredSum.length <= 5000.
1 <= requiredSum[i] <= 31.