3164. Find the Number of Good Pairs II LeetCode Solution
In this guide, you will get 3164. Find the Number of Good Pairs II LeetCode Solution with the best time and space complexity. The solution to Find the Number of Good Pairs II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the Number of Good Pairs II
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
Complexity Analysis
Time Complexity: O(m\sqrt{n})
Space Complexity: O(m)
3164. Find the Number of Good Pairs II LeetCode Solution in C++
class Solution {
public:
long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
unordered_map<int, int> count;
long ans = 0;
for (const int num : nums2)
++count[num * k];
for (const int num : nums1)
for (int divisor = 1; divisor <= sqrt(num); ++divisor)
if (num % divisor == 0) {
ans += count.contains(divisor) ? count[divisor] : 0;
if (num / divisor != divisor)
ans += count.contains(num / divisor) ? count[num / divisor] : 0;
}
return ans;
}
}; /* code provided by PROGIEZ */
3164. Find the Number of Good Pairs II LeetCode Solution in Java
class Solution {
public long numberOfPairs(int[] nums1, int[] nums2, int k) {
HashMap<Integer, Integer> count = new HashMap<>();
long ans = 0;
for (final int num : nums2)
count.merge(num * k, 1, Integer::sum);
for (final int num : nums1)
for (int divisor = 1; divisor <= (int) Math.sqrt(num); ++divisor)
if (num % divisor == 0) {
ans += count.getOrDefault(divisor, 0);
if (num / divisor != divisor)
ans += count.getOrDefault(num / divisor, 0);
}
return ans;
}
} // code provided by PROGIEZ
3164. Find the Number of Good Pairs II LeetCode Solution in Python
class Solution:
def numberOfPairs(self, nums1: list[int], nums2: list[int], k: int) -> int:
count = collections.Counter(num * k for num in nums2)
ans = 0
for num in nums1:
for divisor in range(1, int(num ** 0.5) + 1):
if num % divisor == 0:
ans += count[divisor]
if num // divisor != divisor:
ans += count[num // divisor]
return ans # code by PROGIEZ
