FastPrepCount Nondecreasing Digit-Sum Arrays
Problems/Count Nondecreasing Digit-Sum Arrays

Count Nondecreasing Digit-Sum Arrays

Microsoft logoMicrosoft● HardFULLTIMEOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a Microsoft online assessment. The report gives the rules for digit sums, nondecreasing order, the limit on values, and the modulo, with one example. We chose the method name and the extra examples.

Given an integer array requiredSum of length n, count the arrays result of length n that satisfy all of the following rules:

  • result is nondecreasing, so result[i] <= result[i + 1] for every valid i.
  • For every index i, the sum of the decimal digits of result[i] equals requiredSum[i].
  • Every value in result is between 1 and 5000, inclusive.

Return the number of distinct valid arrays modulo 10^9 + 7.

Function

countDigitSumArrays(requiredSum: int[]) → int

Examples

Example 1

requiredSum = [1]return = 4

The valid one-element arrays are [1], [10], [100], and [1000].

Example 2

requiredSum = [1,1]return = 10

The only eligible values are 1, 10, 100, and 1000. Choosing any two of them with repetition and writing them in nondecreasing order gives 10 arrays.

Example 3

requiredSum = [31,1]return = 0

The only value at most 5000 with digit sum 31 is 4999. No value greater than or equal to 4999 has digit sum 1, so no valid nondecreasing array exists.

Constraints

  • 1 <= requiredSum.length <= 5000.
  • 1 <= requiredSum[i] <= 31.

More Microsoft Online Assessment questions

  • Minimum Cost to Process Priority TasksOA · Seen Nov 2026
  • Most Visited Sprint MarkerOA · Seen Nov 2026
  • Maximum Escape Game ScoreOA · Seen Nov 2026
  • Count Subarrays with a Perfect-Square ProductOA · Seen Nov 2026
  • Maximum Interactive Team SizeOA · Seen Nov 2026
  • Maximize Pipeline Throughput Under a Scaling BudgetOA · Seen Nov 2026
  • Minimum Cost K-Capable ModelsOA · Seen Nov 2026
  • Find Available Meeting RoomsOA · Seen Oct 2026
  • Maximum Sum of a K-StarOA · Seen Oct 2026
  • Capacity to Ship Packages Within DaysOA · ONSITE INTERVIEW · Seen Oct 2026

Similar questions at other companies

  • Stable Workload Redistribution TreesTower Research Capital · OA
  • Count Valid A-B-C Sequences Under a Modulo-Four RuleInfosys · OAInfosys interview questions
  • Count Permutations Without Three Equal Parities in a RowGoogle · OAGoogle interview questions
  • Enough Muffins for the LineSusquehanna International Group (SIG) · OASusquehanna International Group (SIG) interview questions
  • Count Shipment SchedulesMorgan Stanley · OAMorgan Stanley interview questions
  • Find Encrypted NumberAmazon · OA
  • Valid PasswordsMathWorks · OAMathWorks interview questions
  • Coloring HousesSnowflake · OASnowflake interview questions
  • Find Maximum Number of StringsMoveworks · OAMoveworks interview questions
  • Count Distinct Binary Search TreesC3.ai · OAC3.ai interview questions

Microsoft interview experiences

  • Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
  • Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
  • Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
  • Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
  • Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
  • Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public int countDigitSumArrays(int[] requiredSum) {
        // Write your code here.
    }
}
Checking account…