#974
Medium Algorithms Subarray sums divisible by k
Array Hash Table Prefix Sum
56.1% acceptance
Feb 25, 2026
7828
345
Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.
A subarray is a contiguous part of an array.
Solution
Rust
Time O(n)
Space O(n)
impl Solution {
pub fn subarrays_div_by_k(nums: Vec<i32>, k: i32) -> i32 {
let mut counts = vec![0i32; k as usize];
counts[0] = 1;
let mut prefix = 0i32;
let mut ans = 0;
for x in nums {
prefix = ((prefix + x) % k + k) % k;
ans += counts[prefix as usize];
counts[prefix as usize] += 1;
}
ans
}
}