Count non-decreasing arrays by digit sums
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
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.
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].
Input: ([1, 1],)
Expected Output: 10
Explanation: The numbers <= 5000 with digit sum 1 are [1, 10, 100, 1000]. The number of non-decreasing pairs chosen from 4 values with repetition allowed is 10.
Input: ([1, 2],)
Expected Output: 30
Explanation: For first values [1, 10, 100, 1000], the counts of digit-sum-2 values that are at least as large are 10, 9, 7, and 4 respectively. Total = 30.
Input: ([31],)
Expected Output: 1
Explanation: Among integers from 0 to 5000, only 4999 has digit sum 31.
Input: ([31, 0],)
Expected Output: 0
Explanation: The first value must be 4999 and the second value must be 0, which violates the non-decreasing condition.
Input: ([32],)
Expected Output: 0
Explanation: No integer from 0 to 5000 has digit sum 32.
Solution
def solution(required_sums):
MOD = 1_000_000_007
MAX_VALUE = 5000
n = len(required_sums)
if n == 0:
return 1
# Precompute digit sums for all values in [0, 5000].
digit_sum = [0] * (MAX_VALUE + 1)
for x in range(1, MAX_VALUE + 1):
digit_sum[x] = digit_sum[x // 10] + (x % 10)
first = required_sums[0]
if first < 0 or first > 31:
return 0
# prev[v] = number of valid arrays for processed positions ending at value v.
prev = [0] * (MAX_VALUE + 1)
for v in range(MAX_VALUE + 1):
if digit_sum[v] == first:
prev[v] = 1
for i in range(1, n):
s = required_sums[i]
if s < 0 or s > 31:
return 0
curr = [0] * (MAX_VALUE + 1)
running = 0
# For each possible current value v, running is the number of ways
# to choose the previous value <= v.
for v in range(MAX_VALUE + 1):
running += prev[v]
if running >= MOD:
running -= MOD
if digit_sum[v] == s:
curr[v] = running
prev = curr
return sum(prev) % MOD
Time complexity: O(n * 5001). Space complexity: O(5001).
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.