Count day-ranges whose PnL is divisible by m

Question

You have a desk's daily PnL for the year. Count how many contiguous day-ranges have a total that is an exact multiple of m (including zero totals). Count all such ranges in O(n).

Accepted Answer

A range (l, r) sums to a multiple of m exactly when prefix[r+1] and prefix[l] leave the same remainder mod m, since their difference is then divisible by m. So group prefixes by their remainder: any two prefixes in the same remainder bucket bound a valid range. Sweep once, and for each new prefix add the number of earlier prefixes sharing its remainder. Tracing with m = 5: prefixes (with the leading zero) are 0, 4, 9, 9, 7, 14, whose remainders are 0, 4, 4, 4, 2, 4. The remainder 4 appears in four prefixes, contributing \binom{4}{2} = 6 ranges; every other remainder appears once and contribut…

Count day-ranges whose PnL is divisible by m

Your answer

More Coding questions