Count Non-Decreasing Arrays with Prescribed Digit Sums
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Online Assessment
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
```text
requiredSum = [1]
answer = 4
```
The possible values are `1`, `10`, `100`, and `1000`.
### Example 2
```text
requiredSum = [1, 1]
answer = 10
```
Each position can use one of those four values, and ten two-element arrays are non-decreasing.
Overview: Count non-decreasing arrays whose values are at most 5000 and match specified decimal digit sums, returning the total modulo 1000000007.
Read the full Microsoft Software Engineer interview experience this question came from
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
```text
requiredSum = [1]
answer = 4
```
The possible values are `1`, `10`, `100`, and `1000`.
### Example 2
```text
requiredSum = [1, 1]
answer = 10
```
Each position can use one of those four values, and ten two-element arrays are non-decreasing.
Constraints
- 1 <= len(requiredSum) <= 5000.
- Every requiredSum[i] is an integer from 1 through 31.
- Each counted result value is an integer from 1 through 5000, and equal adjacent values are allowed.
- Return the count modulo 1000000007.
Examples
Input: ([1],)
Expected Output: 4
Explanation: Exactly 1, 10, 100, and 1000 have digit sum one.
Input: ([1, 1],)
Expected Output: 10
Explanation: Choosing a non-decreasing pair from four eligible values with repetition gives ten arrays.
Hints
- A valid value at a position must match that position’s required digit sum.
- Equal adjacent values are permitted by the non-decreasing condition.