3164. Find the Number of Good Pairs II

Posted on Edited on In

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:

1
2
3
4
5
6
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:

1
2
3
4
5
6
7
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 <= 10^5
  • 1 <= nums1[i], nums2[j] <= 10^6
  • 1 <= k <= 10^3

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        // since nums1[i] needs to be divisible by k, just divide the nums1 by k and record
        // the numbers in candidates
        unordered_map<int, int> m1, m2;
        for (auto& num1 : nums1) {
            if (num1 % k == 0) {
                m1[num1 / k]++;
            }
        }
        if (m1.empty()) {
            return 0;
        }
        for (auto& num2 : nums2) {
            m2[num2]++;
        }
        int mx = ranges::max_element(m1)->first;
        long long res = 0;
        for (auto& [num2, count] : m2) {
            long long cur = 0;
            for (int i = 1; i * num2 <= mx; i++) {
                int val = i * num2;
                if (m1.contains(val)) {
                    cur += m1[val];
                }
            }
            res += cur * count;
        }
        return res;
    }
};