# Find the Number of Good Pairs II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-number-of-good-pairs-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-the-number-of-good-pairs-ii
**Data structures:** Array, Hash Table
**Companies:** [Airbus SE](https://scaleengineer.com/companies/airbus-se)
---
## 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.

**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`

# Approaches
## Brute Force Iteration
The most straightforward way to solve this problem is to use a brute-force approach. We can simply iterate through every possible pair of elements, one from `nums1` and one from `nums2`, and check if they form a 'good pair' according to the problem's definition. A counter is used to keep track of the total number of such pairs.
**Time:** O(n * m). For each of the `n` elements in `nums1`, we iterate through all `m` elements of `nums2`. Given `n` and `m` can be up to 10<sup>5</sup>, this leads to 10<sup>10</sup> operations in the worst case, which is not feasible. · **Space:** O(1). The space used does not depend on the size of the input arrays, as we only need a single counter variable.
**Pros:** Very simple to understand and implement.; Requires minimal memory (constant space).
**Cons:** Extremely inefficient for the given constraints.; Will result in a 'Time Limit Exceeded' (TLE) error on any reasonably large test case.
### Explanation
This method involves checking every single pair `(i, j)` where `i` is an index for `nums1` and `j` is an index for `nums2`. For each pair, we explicitly compute `nums2[j] * k` and then check if `nums1[i]` is perfectly divisible by this result. We maintain a running total of the pairs that satisfy this condition.

```java
class Solution {
    public long numberOfGoodPairs(int[] nums1, int[] nums2, int k) {
        long goodPairsCount = 0;
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                long divisor = (long) nums2[j] * k;
                // The problem states k is positive, so divisor will not be zero.
                if (nums1[i] % divisor == 0) {
                    goodPairsCount++;
                }
            }
        }
        return goodPairsCount;
    }
}
```
### Algorithm
- Initialize a counter `goodPairsCount` to 0.
- Use a nested loop structure. The outer loop iterates through each element `num1` in `nums1`.
- The inner loop iterates through each element `num2` in `nums2`.
- Inside the inner loop, calculate the potential divisor `d = (long)num2 * k` to prevent integer overflow.
- Check if `num1` is divisible by `d` using the modulo operator: `num1 % d == 0`.
- If the condition is true, increment `goodPairsCount`.
- After both loops complete, return `goodPairsCount`.

## Frequency Map for nums2 and Divisor Enumeration
To improve upon the brute-force method, we can avoid re-scanning `nums2` for every element of `nums1`. We can pre-process `nums2` by storing its elements and their frequencies in a hash map. Then, for each element `num1` in `nums1`, we find all its divisors. For each divisor `d`, we check if it could be formed by some `num2 * k`. This is true if `d` is a multiple of `k`. If so, we calculate the required `num2` value (`d/k`) and add its frequency from the map to our total count.
**Time:** O(m + n * sqrt(max_val)), where `max_val` is the maximum value in `nums1`. Building the map takes O(m). Then, for each of the `n` numbers in `nums1`, we find its divisors in O(sqrt(num)) time. With `n=10^5` and `max_val=10^6`, this is roughly 10<sup>5</sup> * 1000 = 10<sup>8</sup> operations, which is on the edge of timing out. · **Space:** O(U2), where `U2` is the number of unique elements in `nums2`. In the worst case, all elements are unique, leading to O(m) space complexity for the hash map.
**Pros:** Much faster than the naive brute-force approach.; Reduces redundant work by pre-calculating frequencies of numbers in `nums2`.
**Cons:** The time complexity is still high and may result in a 'Time Limit Exceeded' error for the largest constraints.; The performance is dependent on the magnitude of the numbers in `nums1`, not just the length of the array.
### Explanation
The core idea is to change the check from `num1 % (num2 * k) == 0` to finding divisors of `num1`. If `d` is a divisor of `num1`, we need to see if `d` can be represented as `num2 * k` for some `num2` that exists in the `nums2` array. This is equivalent to checking if `d` is divisible by `k` and if `d/k` is a number present in `nums2`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public long numberOfGoodPairs(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> freq2 = new HashMap<>();
        for (int num : nums2) {
            freq2.put(num, freq2.getOrDefault(num, 0) + 1);
        }

        long goodPairsCount = 0;
        for (int num1 : nums1) {
            for (int d = 1; d * d <= num1; d++) {
                if (num1 % d == 0) {
                    // d is a divisor
                    if (d % k == 0) {
                        int val = d / k;
                        goodPairsCount += freq2.getOrDefault(val, 0);
                    }
                    
                    // num1 / d is another divisor
                    int d2 = num1 / d;
                    if (d * d != num1) { // Avoid double counting for perfect squares
                        if (d2 % k == 0) {
                            int val = d2 / k;
                            goodPairsCount += freq2.getOrDefault(val, 0);
                        }
                    }
                }
            }
        }
        return goodPairsCount;
    }
}
```
### Algorithm
- Create a frequency map, `freq2`, for all numbers in `nums2`. A `HashMap` is a good choice for this.
- Initialize a counter `goodPairsCount` to 0.
- Iterate through each number `num1` in `nums1`.
- For each `num1`, find all of its divisors. This can be done by iterating from 1 up to `sqrt(num1)`.
- If `i` divides `num1`, then both `i` and `num1 / i` are divisors.
- For each divisor `d` found:
  - Check if `d` is divisible by `k`.
  - If `d % k == 0`, calculate `val = d / k`.
  - Look up `val` in `freq2`. If it exists, add its frequency `freq2.get(val)` to `goodPairsCount`.
- Be careful to handle perfect squares (when `i * i == num1`) to avoid double-counting.
- Return `goodPairsCount`.

## Optimized Approach with Frequency Maps and Multiples
The most efficient approach involves reversing the logic. Instead of iterating through `nums1` and searching for valid partners in `nums2`, we can iterate through `nums2`, calculate the target divisor `d = num2 * k`, and then efficiently count how many numbers in `nums1` are multiples of `d`. This counting step can be made very fast by pre-computing the frequencies of all numbers in `nums1` and storing them in an array or hash map.
**Time:** O(n + m + max_val + S), where `S` is the sum of `max_val / (num2 * k)` over all unique `num2`. This sum is related to the harmonic series, making it efficient. The overall complexity is dominated by populating the frequency arrays and the nested loops, which is approximately O(n + m + max_val + (max_val/k) * log(max_val)). This is well within the time limits. · **Space:** O(m + max_val), where `max_val` is the maximum value in `nums1`. We need O(m) space for `freq2` in the worst case and O(max_val) for `freq1`. Given `max_val <= 10^6`, this is a feasible memory footprint.
**Pros:** Highly efficient and passes all constraints.; The time complexity is related to a harmonic series, which is very fast in practice.; Effectively handles the problem constraints by changing the perspective of the search.
**Cons:** Requires significant space, proportional to the maximum value in `nums1`, which can be up to 10^6.
### Explanation
We begin by creating frequency maps for both arrays. Let `freq1` be the frequency map for `nums1` and `freq2` for `nums2`. The key insight is to iterate through the smaller set of unique values. We iterate through each unique `num2` from `freq2`. For each `num2`, we calculate `val = num2 * k`. Now, the problem is to count how many numbers in `nums1` are multiples of `val`. With `freq1` pre-computed, we can find this by summing up the frequencies of `val`, `2*val`, `3*val`, etc., up to the maximum value in `nums1`. The total count for a given `num2` is this sum multiplied by the frequency of `num2`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public long numberOfGoodPairs(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> freq2 = new HashMap<>();
        for (int num : nums2) {
            freq2.put(num, freq2.getOrDefault(num, 0) + 1);
        }

        int maxVal = 0;
        for (int num : nums1) {
            if (num > maxVal) {
                maxVal = num;
            }
        }
        
        if (maxVal == 0) { // Edge case for empty nums1 or nums1 with only 0s
            return 0;
        }

        int[] freq1 = new int[maxVal + 1];
        for (int num : nums1) {
            freq1[num]++;
        }

        long goodPairsCount = 0;
        for (Map.Entry<Integer, Integer> entry : freq2.entrySet()) {
            int num2 = entry.getKey();
            int count2 = entry.getValue();
            
            long val = (long) num2 * k;

            for (long multiple = val; multiple <= maxVal; multiple += val) {
                goodPairsCount += (long) freq1[(int)multiple] * count2;
            }
        }
        return goodPairsCount;
    }
}
```
### Algorithm
- First, create a frequency map for the numbers in `nums2`. A `HashMap` is suitable.
- Find the maximum value `maxVal` present in `nums1`.
- Create a frequency array `freq1` of size `maxVal + 1` and populate it with the counts of each number from `nums1`.
- Initialize a counter `goodPairsCount` to 0.
- Iterate through each unique number `num2` and its count `c2` from the `nums2` frequency map.
- For each `num2`, calculate `val = (long)num2 * k`.
- If `val` exceeds `maxVal`, we can skip it, as no number in `nums1` can be a multiple of it.
- Iterate through all multiples of `val` starting from `val` itself, up to `maxVal` (i.e., `m = val, 2*val, 3*val, ...`).
- For each multiple `m`, it represents a valid `num1`. We find how many times `m` appears in `nums1` using `freq1[m]`.
- Add the product `(long)freq1[m] * c2` to `goodPairsCount`.
- Return the final `goodPairsCount`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```