Ezvor

3972. Valid Subarrays With Matching Sum Digits II

HardArray Preparing judge… LeetCode
ArrayHash TableSliding WindowPrefix Sum

Hints

Hint 1
Since all elements are positive, prefix sums are strictly increasing.
Hint 2
A sum has first digit x iff it belongs to one of the ranges [x * 10p, (x + 1) * 10p - 1].
Hint 3
Also require the sum to be congruent to x modulo 10, then count prefix-sum pairs whose difference lies in each valid range and residue class.