How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Count non-decreasing arrays by digit sums | Microsoft Coding Question

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].

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.

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.

Quick Overview

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.