Find the Number of Good Pairs II

Problem

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 (0 <= i <= n - 1, 0 <= j <= m - 1).

Return the total number of good pairs.

Examples

Example 1

Input: nums1 = [1,3,4], nums2 = [1,3,4], k = 1

Output: 5

Explanation:

The 5 good pairs are `(0, 0)`, `(1, 0)`, `(1, 1)`, `(2, 0)`, and `(2, 2)`.

Example 2

Input: nums1 = [1,2,4,12], nums2 = [2,4], k = 3

Output: 2

Explanation:

The 2 good pairs are `(3, 0)` and `(3, 1)`.

Constraints

• 1 <= n, m <= 10^5
• 1 <= nums1[i], nums2[j] <= 10^6
• 1 <= k <= 10^3

Solution

Method 1 – Hash Map for Divisor Counting

Intuition

For each a in nums1, we want to count how many b in nums2 make a % (b * k) == 0. Instead of brute force, we can precompute the frequency of each b in nums2, and for each a, check all divisors of a that are multiples of k and see if b = divisor / k exists in nums2.

Approach

1. Build a frequency map for nums2.
2. For each a in nums1:
   1. For each divisor d of a:
      • If d % k == 0, set b = d // k.
      • If b is in the frequency map, add its count to the answer.
3. Return the total count.

Code

C++

class Solution {
public:
    int numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        unordered_map<int, int> freq;
        for (int b : nums2) freq[b]++;
        int ans = 0;
        for (int a : nums1) {
            for (int d = 1; d * d <= a; ++d) {
                if (a % d == 0) {
                    if (d % k == 0 && freq.count(d / k)) ans += freq[d / k];
                    int d2 = a / d;
                    if (d2 != d && d2 % k == 0 && freq.count(d2 / k)) ans += freq[d2 / k];
                }
            }
        }
        return ans;
    }
};

Go

func numberOfPairs(nums1 []int, nums2 []int, k int) int {
    freq := make(map[int]int)
    for _, b := range nums2 {
        freq[b]++
    }
    ans := 0
    for _, a := range nums1 {
        for d := 1; d*d <= a; d++ {
            if a%d == 0 {
                if d%k == 0 {
                    b := d / k
                    ans += freq[b]
                }
                d2 := a / d
                if d2 != d && d2%k == 0 {
                    b := d2 / k
                    ans += freq[b]
                }
            }
        }
    }
    return ans
}

Java

class Solution {
    public int numberOfPairs(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int b : nums2) freq.put(b, freq.getOrDefault(b, 0) + 1);
        int ans = 0;
        for (int a : nums1) {
            for (int d = 1; d * d <= a; ++d) {
                if (a % d == 0) {
                    if (d % k == 0 && freq.containsKey(d / k)) ans += freq.get(d / k);
                    int d2 = a / d;
                    if (d2 != d && d2 % k == 0 && freq.containsKey(d2 / k)) ans += freq.get(d2 / k);
                }
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun numberOfPairs(nums1: IntArray, nums2: IntArray, k: Int): Int {
        val freq = mutableMapOf<Int, Int>()
        for (b in nums2) freq[b] = freq.getOrDefault(b, 0) + 1
        var ans = 0
        for (a in nums1) {
            var d = 1
            while (d * d <= a) {
                if (a % d == 0) {
                    if (d % k == 0) ans += freq.getOrDefault(d / k, 0)
                    val d2 = a / d
                    if (d2 != d && d2 % k == 0) ans += freq.getOrDefault(d2 / k, 0)
                }
                d++
            }
        }
        return ans
    }
}

Python

class Solution:
    def numberOfPairs(self, nums1: list[int], nums2: list[int], k: int) -> int:
        from collections import Counter
        freq = Counter(nums2)
        ans = 0
        for a in nums1:
            d = 1
            while d * d <= a:
                if a % d == 0:
                    if d % k == 0:
                        b = d // k
                        ans += freq.get(b, 0)
                    d2 = a // d
                    if d2 != d and d2 % k == 0:
                        b2 = d2 // k
                        ans += freq.get(b2, 0)
                d += 1
        return ans

Rust

use std::collections::HashMap;
impl Solution {
    pub fn number_of_pairs(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i32 {
        let mut freq = HashMap::new();
        for &b in &nums2 {
            *freq.entry(b).or_insert(0) += 1;
        }
        let mut ans = 0;
        for &a in &nums1 {
            let mut d = 1;
            while d * d <= a {
                if a % d == 0 {
                    if d % k == 0 {
                        let b = d / k;
                        ans += *freq.get(&b).unwrap_or(&0);
                    }
                    let d2 = a / d;
                    if d2 != d && d2 % k == 0 {
                        let b2 = d2 / k;
                        ans += *freq.get(&b2).unwrap_or(&0);
                    }
                }
                d += 1;
            }
        }
        ans
    }
}

TypeScript

class Solution {
    numberOfPairs(nums1: number[], nums2: number[], k: number): number {
        const freq = new Map<number, number>();
        for (const b of nums2) freq.set(b, (freq.get(b) || 0) + 1);
        let ans = 0;
        for (const a of nums1) {
            for (let d = 1; d * d <= a; ++d) {
                if (a % d === 0) {
                    if (d % k === 0) ans += freq.get(d / k) || 0;
                    const d2 = a / d;
                    if (d2 !== d && d2 % k === 0) ans += freq.get(d2 / k) || 0;
                }
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n * sqrt(A) + m), where n is the length of nums1, m is the length of nums2, and A is the maximum value in nums1. For each a in nums1, we check all its divisors.
• 🧺 Space complexity: O(M), where M is the number of unique elements in nums2 (for the frequency map).