3164. Find the Number of Good Pairs II

Problem Link

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 <= 105
• 1 <= nums1[i], nums2[j] <= 106
• 1 <= k <= 103

Solution

---

Python3

factors = [[] for _ in range(10 ** 6 + 1)]
for i in range(1, 10 ** 6 + 1):
    for j in range(i, 10 ** 6 + 1, i):
        factors[j].append(i)
 
class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        nums1 = [num // k for num in nums1 if num % k == 0]
        nums2 = Counter(nums2)
 
        res = 0
        for num in nums1:
            for factor in factors[num]:
                res += nums2[factor]
                
        return res

C++

class Solution {
public:
    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        long long ans = 0;
        unordered_map<int, int> mp;
 
        for (auto& x : nums2) mp[x * k]++;
 
        for (auto& x : nums1) {
            for (int d = 1; d * d <= x; d++) {
                if (x % d == 0) {
                    ans += (long long) mp[d];
                    if (d != (x / d)) ans += (long long) mp[x / d];
                }
            }
        }
 
        return ans;
    }
};