Skip to main content
Back to problems
#3164
Medium Algorithms

Find the number of good pairs ii

Array Hash Table
26.6% acceptance
Feb 24, 2026
253
40
You are given 2 integer arrays nums1 and nums2 of lengths n and m respectively. You are also given a positive integer k. A pair (i, j) is called good if nums1[i] is divisible by nums2[j] * k. Return the total number of good pairs.

Solution

Rust
Time O(n²)
Space O(n)
LeetCode
solution.rs 
impl Solution {
  pub fn number_of_pairs(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i64 {
    const MAX_VAL: usize = 1_000_001;
    let mut freq1 = vec![0i64; MAX_VAL];
    for &x in &nums1 {
      freq1[x as usize] += 1;
    }
    let k = k as i64;
    let mut result = 0i64;
    // For each unique d = nums2[j] * k, count multiples of d in freq1
    // Deduplicate nums2 with counts to avoid redundant computation
    let mut freq2 = std::collections::HashMap::new();
    for &y in &nums2 {
      *freq2.entry(y as i64).or_insert(0i64) += 1;
    }
    for (y, cnt) in freq2 {
      let d = y * k;
      if d >= MAX_VAL as i64 {
        continue;
      }
      let mut m = d;
      while m < MAX_VAL as i64 {
        result += freq1[m as usize] * cnt;
        m += d;
      }
    }
    result
  }
}