Katkat
Back

Count non-decreasing arrays by digit sums

MicrosoftSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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