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