Count of interesting subarrays

Array Hash Table Prefix Sum

58.0% acceptance

Feb 25, 2026

966

270

You are given a 0-indexed integer array nums, an integer modulo, and an integer k. Your task is to find the count of subarrays that are interesting. A subarray nums[l..r] is interesting if the following condition holds: Let cnt be the number of indices i in the range [l, r] such that nums[i] % modulo == k. Then, cnt % modulo == k. Return an integer denoting the count of interesting subarrays. Note: A subarray is a contiguous non-empty sequence of elements within an array.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_interesting_subarrays(nums: Vec<i32>, modulo: i32, k: i32) -> i64 {
    use std::collections::HashMap;
    let modulo = modulo as i64;
    let k = k as i64;
    let mut prefix_count: HashMap<i64, i64> = HashMap::new();
    prefix_count.insert(0, 1);
    let mut cnt = 0i64;
    let mut ans = 0i64;
    for &v in &nums {
      if v as i64 % modulo == k { cnt = (cnt + 1) % modulo; }
      // We need (cnt - prev_cnt) % modulo == k => prev_cnt == (cnt - k + modulo) % modulo
      let need = (cnt - k + modulo) % modulo;
      ans += prefix_count.get(&need).cloned().unwrap_or(0);
      *prefix_count.entry(cnt).or_insert(0) += 1;
    }
    ans
  }
}