Count array pairs divisible by k

Array Hash Table Math Counting Number Theory

30.6% acceptance

Feb 25, 2026

923

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs (i, j) such that: 0 <= i < j <= n - 1 and nums[i] * nums[j] is divisible by k.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_pairs(nums: Vec<i32>, k: i32) -> i64 {
    fn gcd(a: usize, b: usize) -> usize {
      if b == 0 { a } else { gcd(b, a % b) }
    }

    let k = k as usize;
    let max_val = *nums.iter().max().unwrap() as usize;

    // freq[v] = count of v in nums
    let mut freq = vec![0i64; max_val + 1];
    for &v in &nums {
      freq[v as usize] += 1;
    }

    // cnt_div[d] = count of elements divisible by d
    let mut cnt_div = vec![0i64; max_val + 1];
    for d in 1..=max_val {
      let mut v = d;
      while v <= max_val {
        cnt_div[d] += freq[v];
        v += d;
      }
    }

    // For each element, needed = k / gcd(nums[i], k)
    // Pair (i,j) valid iff needed_i | nums[j]
    // Total = (sum_i cnt_div[needed_i] - count_self) / 2
    let mut total = 0i64;
    let mut self_count = 0i64;
    for &v in &nums {
      let v = v as usize;
      let g = gcd(v, k);
      let needed = k / g;
      if needed <= max_val {
        total += cnt_div[needed];
        if v % needed == 0 {
          self_count += 1;
        }
      }
    }
    (total - self_count) / 2
  }
}