Count non-decreasing arrays by digit sums
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an array required_sums of length n. Count how many non-decreasing arrays result[1..n] of integers satisfy all of the following:
(
1) for each i, digit_sum(result[i]) = required_sums[i];
(
2) for each i, result[i] ≤ 5000; and
(
3) for i > 1, result[i] ≥ result[i−1]. Two arrays are distinct if they differ at any index. Return the count modulo 1,000,000,007. Describe an efficient algorithm and analyze its time and space complexity.
Quick Answer: This question evaluates combinatorics and constrained counting skills, including reasoning about digit-sum properties, monotonic sequences, modular arithmetic, and efficient algorithm design within the Coding & Algorithms domain.
You are given an integer array required_sums of length n. Count how many arrays result of the same length satisfy all of the following: (1) result is non-decreasing, (2) every value is an integer between 0 and 5000 inclusive, and (3) digit_sum(result[i]) == required_sums[i] for every index i. Two arrays are different if they differ at any index. Return the count modulo 1,000,000,007. Define digit_sum(0) = 0. If required_sums is empty, the answer is 1 because the empty array is valid.
Constraints
- 0 <= len(required_sums) <= 2000
- Each required_sums[i] is an integer; for values in [0, 5000], achievable digit sums are only from 0 to 31
- Every result[i] must satisfy 0 <= result[i] <= 5000
Examples
Input: ([],)
Expected Output: 1
Explanation: There is exactly one array of length 0: the empty array.
Input: ([0, 0, 0],)
Expected Output: 1
Explanation: Only the number 0 has digit sum 0, so the only valid non-decreasing array is [0, 0, 0].
Hints
- The possible values for each result[i] are limited to 0 through 5000, so try dynamic programming over the chosen value instead of over arbitrary integers.
- If dp[v] is the number of ways to end the previous position with value v, then for a new value x you need the sum of all dp[v] where v <= x. A running prefix sum lets you compute this efficiently.