Find the Number of Good Pairs I
EasyPrompt
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 <= 501 <= nums1[i], nums2[j] <= 501 <= k <= 50
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward way to solve this problem is to use a brute-force approach. We can iterate through every possible pair of elements, one from nums1 and one from nums2, and check if they satisfy the given condition. This method is easy to understand and implement, directly translating the problem's definition into code.
Algorithm
- Initialize a counter variable,
count, to 0. - Use a nested loop structure. The outer loop iterates through each element
num1innums1. - The inner loop iterates through each element
num2innums2. - Inside the inner loop, calculate the divisor
d = num2 * k. - Check if
num1is divisible bydusing the modulo operator (num1 % d == 0). - If the condition is true, increment the
count. - After both loops have finished, return the final
count.
Walkthrough
This approach involves two nested loops. The outer loop iterates through each element nums1[i] of the first array, and the inner loop iterates through each element nums2[j] of the second array. For every pair (i, j), we calculate the value nums2[j] * k. Then, we check if nums1[i] is divisible by this value. If it is, we increment a counter. We repeat this for all possible pairs. After checking all pairs, the value of the counter is our answer.
class Solution { public int numberOfPairs(int[] nums1, int[] nums2, int k) { int n = nums1.length; int m = nums2.length; int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { long divisor = (long) nums2[j] * k; if (nums1[i] % divisor == 0) { count++; } } } return count; }}Note: We use long for the divisor to prevent potential integer overflow, although with the given constraints (50 * 50 = 2500), an int would suffice.
Complexity
Time
O(n * m), where `n` is the length of `nums1` and `m` is the length of `nums2`. This is because we iterate through each element of `nums1` and for each of them, we iterate through all elements of `nums2`.
Space
O(1) extra space. We only need a single variable to keep track of the count of good pairs.
Trade-offs
Pros
It is very simple to conceptualize and write.
It uses constant extra space, O(1), making it very memory-efficient.
Cons
This approach has a time complexity of O(n * m), which can be slow if the input arrays
nums1andnums2are very large.It performs redundant calculations if there are duplicate numbers in the arrays.
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.