Windows With a Divisible Sum

Medium

You are given an array of integers values (negatives and zeros allowed) and a number divisor. A window is a non-empty run of consecutive elements. Count the windows whose sum is evenly divisible by divisor. Windows at different positions count separately, even if their values match. Checking every window takes O(n²); try to find an O(n) solution.

Example 1

values=[3, -1, 4, 2], divisor=3 → 4

Four windows have a sum divisible by 3: [3] = 3, [-1, 4] = 3, [4, 2] = 6 and [3, -1, 4] = 6.

Example 2

values=[5], divisor=2 → 0

The only window sums to 5, which is odd.

Example 3

values=[0, 0], divisor=7 → 3

Zero is divisible by anything, so all three windows count: [0], [0] and [0, 0].

Constraints

1 ≤ len(values) ≤ 3·10⁴
-10⁴ ≤ values[i] ≤ 10⁴
2 ≤ divisor ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Prefix Sum

Similar problems

Longest Run with a Given Sum Medium A Stretch Divisible by k Medium As Many Heads as Tails Medium Stretches With an Exact Total Medium Windows With an Exact Alarm Count Medium

Input

values=[3, -1, 4, 2], divisor=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 109 tests on the server, hidden ones included.