Number of divisible triplet sums

Array Hash Table

67.5% acceptance

Mar 31, 2026

Given a 0-indexed integer array nums and an integer d, return the number of triplets (i, j, k) such that i < j < k and (nums[i] + nums[j] + nums[k]) % d == 0.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn divisible_triplet_count(nums: Vec<i32>, d: i32) -> i32 {
    let n = nums.len();
    let d = d as i64;
    let mut count = 0;
    let mut freq = std::collections::HashMap::new();
    for j in 0..n {
      for k in j + 1..n {
        let sum = (nums[j] as i64 + nums[k] as i64) % d;
        let need = (d - sum) % d;
        count += freq.get(&need).unwrap_or(&0);
      }
      let r = nums[j] as i64 % d;
      *freq.entry(r).or_insert(0) += 1;
    }
    count
  }
}