Skip to content

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 digit pairs $(x, y)$ and check whether $x \bmod (y \times k) = 0$. If it satisfies the condition, increment the answer by one.

After the enumeration is complete, return the answer.

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

1
2
3
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)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

Solution 2: 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, \textit{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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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