# 3164. Find the Number of Good Pairs II

## Description

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.

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 <= 105
• 1 <= nums1[i], nums2[j] <= 106
• 1 <= k <= 103

## Solutions

### Solution 1: Hash Table + Enumerate Multiples

We use a hash table cnt1 to record the occurrence times of each number divided by $k$ in array nums1, and a hash table cnt2 to record the occurrence times of each number in array nums2.

Next, we enumerate each number $x$ in array nums2. For each number $x$, we enumerate its multiples $y$, where the range of $y$ is $[x, \text{mx}]$, where mx is the maximum key value in cnt1. Then we count the sum of cnt1[y], denoted as $s$. Finally, we add $s \times v$ to the answer, where $v$ is cnt2[x].

The time complexity is $O(n + m + (M / k) \times \log m)$, and the space complexity is $O(n + m)$. Where $n$ and $m$ are the lengths of arrays nums1 and nums2 respectively, and $M$ is the maximum value in array nums1.

• class Solution {
public long numberOfPairs(int[] nums1, int[] nums2, int k) {
Map<Integer, Integer> cnt1 = new HashMap<>();
for (int x : nums1) {
if (x % k == 0) {
cnt1.merge(x / k, 1, Integer::sum);
}
}
if (cnt1.isEmpty()) {
return 0;
}
Map<Integer, Integer> cnt2 = new HashMap<>();
for (int x : nums2) {
cnt2.merge(x, 1, Integer::sum);
}
long ans = 0;
int mx = Collections.max(cnt1.keySet());
for (var e : cnt2.entrySet()) {
int x = e.getKey(), v = e.getValue();
int s = 0;
for (int y = x; y <= mx; y += x) {
s += cnt1.getOrDefault(y, 0);
}
ans += 1L * s * v;
}
return ans;
}
}

• class Solution {
public:
long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
unordered_map<int, int> cnt1;
for (int x : nums1) {
if (x % k == 0) {
cnt1[x / k]++;
}
}
if (cnt1.empty()) {
return 0;
}
unordered_map<int, int> cnt2;
for (int x : nums2) {
++cnt2[x];
}
int mx = 0;
for (auto& [x, _] : cnt1) {
mx = max(mx, x);
}
long long ans = 0;
for (auto& [x, v] : cnt2) {
long long s = 0;
for (int y = x; y <= mx; y += x) {
s += cnt1[y];
}
ans += s * v;
}
return ans;
}
};

• class Solution:
def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
cnt1 = Counter(x // k for x in nums1 if x % k == 0)
if not cnt1:
return 0
cnt2 = Counter(nums2)
ans = 0
mx = max(cnt1)
for x, v in cnt2.items():
s = sum(cnt1[y] for y in range(x, mx + 1, x))
ans += s * v
return ans


• func numberOfPairs(nums1 []int, nums2 []int, k int) (ans int64) {
cnt1 := map[int]int{}
for _, x := range nums1 {
if x%k == 0 {
cnt1[x/k]++
}
}
if len(cnt1) == 0 {
return 0
}
cnt2 := map[int]int{}
for _, x := range nums2 {
cnt2[x]++
}
mx := 0
for x := range cnt1 {
mx = max(mx, x)
}
for x, v := range cnt2 {
s := 0
for y := x; y <= mx; y += x {
s += cnt1[y]
}
ans += int64(s) * int64(v)
}
return
}

• function numberOfPairs(nums1: number[], nums2: number[], k: number): number {
const cnt1: Map<number, number> = new Map();
for (const x of nums1) {
if (x % k === 0) {
cnt1.set((x / k) | 0, (cnt1.get((x / k) | 0) || 0) + 1);
}
}
if (cnt1.size === 0) {
return 0;
}
const cnt2: Map<number, number> = new Map();
for (const x of nums2) {
cnt2.set(x, (cnt2.get(x) || 0) + 1);
}
const mx = Math.max(...cnt1.keys());
let ans = 0;
for (const [x, v] of cnt2) {
let s = 0;
for (let y = x; y <= mx; y += x) {
s += cnt1.get(y) || 0;
}
ans += s * v;
}
return ans;
}