Katkat
Back

Count Non-Decreasing Arrays with Prescribed Digit Sums

MicrosoftSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Count non-decreasing arrays whose values are at most 5000 and match specified decimal digit sums, returning the total modulo 1000000007.

Given an integer array requiredSum of length n, count the distinct arrays result of length n that satisfy all three conditions:

  1. result is non-decreasing: result[i] <= result[i + 1] for every adjacent pair.
  2. The sum of the base-10 digits of result[i] equals requiredSum[i] at every position.
  3. 1 <= result[i] <= 5000 at every position.

Return the count modulo 1000000007. Two arrays are distinct if they differ at any position. Equal adjacent values are allowed.

Input and Output

  • Input: the integer array requiredSum.
  • Output: one integer, the number of valid arrays modulo 1000000007. No particular valid array is required.

Constraints

  • 1 <= n <= 5000.
  • 1 <= requiredSum[i] <= 31 for every index.

Example 1

requiredSum = [1]
answer = 4

The possible values are 1, 10, 100, and 1000.

Example 2

requiredSum = [1, 1]
answer = 10

Each position can use one of those four values, and ten two-element arrays are non-decreasing.