# 3162. Find the Number of Good Pairs I

## 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 <= 50
• 1 <= nums1[i], nums2[j] <= 50
• 1 <= k <= 50

## Solutions

### Solution 1: Brute Force Enumeration

We directly enumerate all digits $(x, y)$, and check whether $x \mod (y \times k) = 0$. If it is, we increment the answer.

After the enumeration ends, we return the answer.

The time complexity is $O(m \times n)$, where $m$ and $n$ are the lengths of arrays nums1 and nums2 respectively. The space complexity is $O(1)$.

• 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;
}
}

• 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;
}
};

• 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)


• func numberOfPairs(nums1 []int, nums2 []int, k int) (ans int) {
for _, x := range nums1 {
for _, y := range nums2 {
if x%(y*k) == 0 {
ans++
}
}
}
return
}

• function numberOfPairs(nums1: number[], nums2: number[], k: number): number {
let ans = 0;
for (const x of nums1) {
for (const y of nums2) {
if (x % (y * k) === 0) {
++ans;
}
}
}
return ans;
}