Skip to main content
Back to problems
#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)
LeetCode
solution.rs
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
  }
}