Make sum divisible by p

Array Hash Table Prefix Sum

42.6% acceptance

Feb 25, 2026

2856

195

Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array. Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_subarray(nums: Vec<i32>, p: i32) -> i32 {
    let p = p as i64;
    let total: i64 = nums.iter().map(|&x| x as i64).sum();
    let need = total % p;
    if need == 0 {
      return 0;
    }
    let n = nums.len();
    let mut prefix_mod = std::collections::HashMap::new();
    prefix_mod.insert(0i64, 0usize);
    let mut cur: i64 = 0;
    let mut ans = n; // starting with n means impossible (can't remove all)
    for (i, &x) in nums.iter().enumerate() {
      cur = (cur + x as i64) % p;
      // We want cur - need ≡ 0 (mod p), i.e. prefix[j] = (cur - need + p) % p
      let target = (cur - need + p) % p;
      if let Some(&j) = prefix_mod.get(&target) {
        ans = ans.min(i + 1 - j);
      }
      prefix_mod.insert(cur, i + 1);
    }
    if ans == n {
      -1
    } else {
      ans as i32
    }
  }
}