FAANG · LeetCode #974

Subarray Sums Divisible by K — three-stage drill

1The ProblemMedium

Subarray Sums Divisible by K

Count contiguous subarrays whose sum is divisible by k.

Examples

[4,5,0,-2,-3,1], k=5→ 7[1,2,3], k=7→ 0

constraintValues may be negative (use ((p % k) + k) % k).

2The PatternTIME O(n) · SPACE O(n)

Prefix Sum

Running cumulative totals turn range-sum questions into O(1) lookups.

Problems using this pattern

3The SolutionRESULT → 7

Step through it

start: seen = {0: 1}, count = 0

Step 1 / 8

Python▎prefix % k + map lookup

1def subarraysDivByK(nums, k):
2    count = 0
3    prefix = 0
4    seen = {0: 1}
5    for x in nums:
6        prefix += x
7        r = (prefix % k + k) % k
8        count += seen.get(r, 0)
9        seen[r] = seen.get(r, 0) + 1
10    return count

why it worksA subarray (j, i] is divisible by k exactly when prefix[i] and prefix[j] have the SAME remainder mod k (their difference is a multiple of k). So count remainders in a map just like #560 counts prefix sums — count += seen[prefix % k].

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Subarray Sums Divisible by K — three-stage drill