Count Nondecreasing Digit-Sum Arrays
Updated
Problem statement
Given an integer array requiredSum of length n, count the arrays result of length n that satisfy all of the following rules:
resultis nondecreasing, soresult[i] <= result[i + 1]for every validi.- For every index
i, the sum of the decimal digits ofresult[i]equalsrequiredSum[i]. - Every value in
resultis between1and5000, inclusive.
Return the number of distinct valid arrays modulo 10^9 + 7.
Function
countDigitSumArrays(requiredSum: int[]) → intExamples
Example 1
requiredSum = [1]return = 4The valid one-element arrays are [1], [10], [100], and [1000].
Example 2
requiredSum = [1,1]return = 10The 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 = 0The 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)