python-subarray-divisible-negative-mod
The trap. For a positive divisor, Python's % is already the mathematical modulo: -1 % 3 == 2, i.e. the remainder always lands in [0, k-1]. So the correct fix is to do no remainder normalization at all — attempts to "fix" negative sums, like abs(prefix) % k or C-style truncation plus +k hacks, push negative prefix sums into the wrong bucket. Example: prefix -1, k=3 should bucket to remainder 2; abs(-1) % 3 == 1 buckets it wrongly and a subarray like [2] (remainder 1) gets falsely counted as divisible (brute force says 0, naive says 1).
Other real pitfalls the classic solution hits:
- k up to 1e9 → a fixed-size remainder array is infeasible; use a dict.
- If k can be negative, normalize k = abs(k) once (divisibility by k ≡ divisibility by -k); then Python's % returns canonical buckets in [0, k-1] with no extra work.
- The empty prefix (sum 0, remainder 0) must be seeded into the buckets or subarrays starting at index 0 are lost.
from collections import defaultdict
from typing import List
def count_divisible_subarrays(arr: List[int], k: int) -> int:
if k == 0:
raise ValueError("k must be nonzero (division by zero is undefined)")
k = abs(k) # divisibility by k == divisibility by -k
buckets = defaultdict(int)
buckets[0] = 1 # empty prefix sum; counts subarrays starting at index 0
prefix = 0
count = 0
for x in arr:
prefix += x
r = prefix % k # Python: always in [0, k-1] for k > 0 ← no normalization
count += buckets[r] # previous prefixes congruent to prefix (mod k)
buckets[r] += 1
return count
Why it's correct. Let P[i] = sum(arr[0..i]). A subarray arr[i..j] has sum P[j] - P[i-1], divisible by k iff P[j] ≡ P[i-1] (mod k). Iterating j left-to-right, count adds the number of earlier prefixes (including the empty one) in the same remainder bucket — one pass, O(n) time, O(n) space.
Contrast with the broken naive version (for illustration):
def naive_broken(arr, k): # WRONG: abs() before modulo
buckets = {0: 1}; prefix = 0; count = 0
for x in arr:
prefix += x
r = abs(prefix) % k # -1 % 3 → 1 instead of 2 → wrong bucket
count += buckets.get(r, 0)
buckets[r] = buckets.get(r, 0) + 1
return count
Verified with a randomized brute-force differential harness (`brute`: O(n²) enumeration of every subarray) plus exhaustive and closed-form cases:
1. **Exhaustive:** every array in `{-2..2}^n` for `n = 1..6` × every `k = 1..6` → **117,180 checks**, all match.
2. **Random differential:** 20,000 trials, `n ∈ [0, 60]`, elements in `[-1000, 1000]`, `k` drawn from `[1,12]`, `[1,10⁶]`, `[1,10⁹]`, `1`, `2`, and **negative** k (`-12..-1`, `-10⁹`) — all match the O(n²) reference exactly.
3. **Edge cases:** empty array → 0; `[0]`→1; `[0,0,0]`, k=7 → 6 (= n(n+1)/2); `[5]`,k=5 → 1; `[5]`,k=7 → 0; `[1,2,3]`,k=3 → 3; `[-1,-2,-3]`,k=3 → 3 (negative mirror); `[1,-1,1,-1]`,k=2 → 4; `[10⁹,-10⁹,10⁹]`,k=10⁹ → 6; `[-10⁹]×3`,k=10⁹ → 6; `[3,1,2,-4,5]`,k=3 → 4.
4. **Closed form:** all-zero arrays of length 1, 2, 10, 100, 1000 × k ∈ {1,2,3,10⁹} → exactly `n(n+1)/2`.
5. **k = 0:** raises `ValueError` (division-by-zero is undefined).
6. **Perf:** 2,000,000 random elements in `[-10⁹,10⁹]`, k=10⁹ → **0.671 s**, single pass (prefix of it cross-checked against brute force).
7. **Failure-mode confirmed:** the naive `abs(prefix) % k` variant disagrees with brute force on concrete cases, e.g. `[-1, 2]`, k=3 → naive 1, correct 0; `[-2, 3]`, k=3 → naive 0, correct 1 — exactly the off-by-one under/overcounts the prompt warns about.
**Result: 137,213 checks, all passed** (117,180 exhaustive + 20,000 random + edge/closed-form/perf).{"model": "deepseek-v4-flash", "problem_class": "python-subarray-divisible-negative-mod", "result": "passed", "tests": 137213}