# Find the Number of Good Pairs I
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-number-of-good-pairs-i)
Canonical: https://scaleengineer.com/dsa/problems/find-the-number-of-good-pairs-i
**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 <= 50`
* `1 <= nums1[i], nums2[j] <= 50`
* `1 <= k <= 50`

# Approaches
## Brute-Force Nested Loops
The most straightforward way to solve this problem is to use a brute-force approach. We can iterate through every possible pair of elements, one from `nums1` and one from `nums2`, and check if they satisfy the given condition. This method is easy to understand and implement, directly translating the problem's definition into code.
**Time:** O(n * m), where `n` is the length of `nums1` and `m` is the length of `nums2`. This is because we iterate through each element of `nums1` and for each of them, we iterate through all elements of `nums2`. · **Space:** O(1) extra space. We only need a single variable to keep track of the count of good pairs.
**Pros:** It is very simple to conceptualize and write.; It uses constant extra space, O(1), making it very memory-efficient.
**Cons:** This approach has a time complexity of O(n * m), which can be slow if the input arrays `nums1` and `nums2` are very large.; It performs redundant calculations if there are duplicate numbers in the arrays.
### Explanation
This approach involves two nested loops. The outer loop iterates through each element `nums1[i]` of the first array, and the inner loop iterates through each element `nums2[j]` of the second array. For every pair `(i, j)`, we calculate the value `nums2[j] * k`. Then, we check if `nums1[i]` is divisible by this value. If it is, we increment a counter. We repeat this for all possible pairs. After checking all pairs, the value of the counter is our answer.

```java
class Solution {
    public int numberOfPairs(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        int m = nums2.length;
        int count = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                long divisor = (long) nums2[j] * k;
                if (nums1[i] % divisor == 0) {
                    count++;
                }
            }
        }

        return count;
    }
}
```
Note: We use `long` for the `divisor` to prevent potential integer overflow, although with the given constraints (`50 * 50 = 2500`), an `int` would suffice.
### Algorithm
- Initialize a counter variable, `count`, 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 divisor `d = num2 * k`.
- Check if `num1` is divisible by `d` using the modulo operator (`num1 % d == 0`).
- If the condition is true, increment the `count`.
- After both loops have finished, return the final `count`.

## Optimized Approach using Frequency Map
A more efficient approach involves pre-processing one of the arrays to avoid repeated computations. Given the small constraints on the values of the numbers (1 to 50), we can use a frequency map (or a simple array) to store the counts of each number in `nums1`. Then, for each number in `nums2`, we can efficiently find how many numbers in `nums1` form a good pair with it.
**Time:** O(n + m * (MAX_VAL / k)). The first term `n` is for building the frequency map. The second term is for iterating through `nums2` (`m` times), and for each, iterating through multiples. The number of multiples of `d` up to `MAX_VAL` is `MAX_VAL / d`. Since `d >= k`, this inner loop runs at most `MAX_VAL / k` times. Given the constraints, this is effectively O(n + m). · **Space:** O(C), where C is the maximum possible value in the arrays. Given the constraint that numbers are at most 50, this is O(51), which simplifies to O(1) constant space.
**Pros:** Significantly more time-efficient with a complexity of O(n + m), which is much better than O(n * m) for the given constraints.; Handles duplicate values efficiently by pre-calculating frequencies.
**Cons:** This approach's space complexity depends on the maximum possible value in the input arrays. If the numbers could be very large, it would require a large frequency array or a hash map, increasing space usage.; The implementation is slightly more complex than the brute-force approach.
### Explanation
The key optimization is to avoid the inner loop over `nums1` for every element of `nums2`. We can achieve this by first counting the occurrences of each number in `nums1`.

1.  Create a frequency array, `freq1`, of size 51 (to hold counts for numbers 1 through 50).
2.  Iterate through `nums1` and populate `freq1`. For example, `freq1[12]` will store how many times 12 appears in `nums1`.
3.  Initialize a `count` of good pairs to 0.
4.  Now, iterate through `nums2`. For each `num2`, calculate the required divisor `d = num2 * k`.
5.  We need to find how many numbers in `nums1` are multiples of `d`. Instead of iterating through `nums1` again, we can iterate through the multiples of `d` (i.e., `d`, `2*d`, `3*d`, etc.) up to the maximum value of 50. For each such `multiple`, we look up its count in our `freq1` array and add it to our total `count`.

This way, we avoid the O(n) scan for each of the `m` elements, replacing it with a much faster lookup based on multiples.

```java
class Solution {
    public int numberOfPairs(int[] nums1, int[] nums2, int k) {
        int[] freq1 = new int[51];
        for (int num : nums1) {
            freq1[num]++;
        }

        int count = 0;
        for (int num2 : nums2) {
            long divisor = (long) num2 * k;
            // Iterate through all multiples of 'divisor' that are within the range [1, 50]
            for (long multiple = divisor; multiple <= 50; multiple += divisor) {
                count += freq1[(int)multiple];
            }
        }

        return count;
    }
}
```
### Algorithm
- Since the values in `nums1` are small (1 to 50), create a frequency array `freq1` of size 51.
- Iterate through `nums1` and populate `freq1`. `freq1[x]` will store the number of occurrences of `x` in `nums1`.
- Initialize a counter `count` to 0.
- Iterate through each element `num2` in the `nums2` array.
- For each `num2`, calculate the divisor `d = num2 * k`.
- If `d` is greater than 50, no number in `nums1` can be a multiple of it, so we can continue to the next `num2`.
- Otherwise, iterate through all multiples of `d` up to 50. For each `multiple` (i.e., `d`, `2*d`, `3*d`, ...), add its frequency `freq1[multiple]` to the total `count`.
- Return the final `count`.

# Solutions
### Java

```java
class Solution {
public
  int numberOfPairs(int[] nums1, int[] nums2, int k) {
    int ans = 0;
    for (int x : nums1) {
      for (int y : nums2) {
        if (x % (y * k) == 0) {
          ++ans;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfPairs(vector<int> &nums1, vector<int> &nums2, int k) {
    int ans = 0;
    for (int x : nums1) {
      for (int y : nums2) {
        if (x % (y * k) == 0) {
          ++ans;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int: return sum(
        x % (y * k) == 0 for x in nums1 for y in nums2)

```