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.
A more efficient approach involves pre-processing one of the arrays to avoid repeated computations. Given the small constraints on the values of the numbers (1 to 50), we can use a frequency map (or a simple array) to store the counts of each number in nums1. Then, for each number in nums2, we can efficiently find how many numbers in nums1 form a good pair with it.
Algorithm
- Since the values in
nums1are small (1 to 50), create a frequency arrayfreq1of size 51. - Iterate through
nums1and populatefreq1.freq1[x]will store the number of occurrences ofxinnums1. - Initialize a counter
countto 0. - Iterate through each element
num2in thenums2array. - For each
num2, calculate the divisord = num2 * k. - If
dis greater than 50, no number innums1can be a multiple of it, so we can continue to the nextnum2. - Otherwise, iterate through all multiples of
dup to 50. For eachmultiple(i.e.,d,2*d,3*d, ...), add its frequencyfreq1[multiple]to the totalcount. - Return the final
count.
Walkthrough
The key optimization is to avoid the inner loop over nums1 for every element of nums2. We can achieve this by first counting the occurrences of each number in nums1.
- Create a frequency array,
freq1, of size 51 (to hold counts for numbers 1 through 50). - Iterate through
nums1and populatefreq1. For example,freq1[12]will store how many times 12 appears innums1. - Initialize a
countof good pairs to 0. - Now, iterate through
nums2. For eachnum2, calculate the required divisord = num2 * k. - We need to find how many numbers in
nums1are multiples ofd. Instead of iterating throughnums1again, we can iterate through the multiples ofd(i.e.,d,2*d,3*d, etc.) up to the maximum value of 50. For each suchmultiple, we look up its count in ourfreq1array and add it to our totalcount.
This way, we avoid the O(n) scan for each of the m elements, replacing it with a much faster lookup based on multiples.
class Solution { public int numberOfPairs(int[] nums1, int[] nums2, int k) { int[] freq1 = new int[51]; for (int num : nums1) { freq1[num]++; } int count = 0; for (int num2 : nums2) { long divisor = (long) num2 * k; // Iterate through all multiples of 'divisor' that are within the range [1, 50] for (long multiple = divisor; multiple <= 50; multiple += divisor) { count += freq1[(int)multiple]; } } return count; }}Complexity
Time
O(n + m * (MAX_VAL / k)). The first term `n` is for building the frequency map. The second term is for iterating through `nums2` (`m` times), and for each, iterating through multiples. The number of multiples of `d` up to `MAX_VAL` is `MAX_VAL / d`. Since `d >= k`, this inner loop runs at most `MAX_VAL / k` times. Given the constraints, this is effectively O(n + m).
Space
O(C), where C is the maximum possible value in the arrays. Given the constraint that numbers are at most 50, this is O(51), which simplifies to O(1) constant space.
Trade-offs
Pros
Significantly more time-efficient with a complexity of O(n + m), which is much better than O(n * m) for the given constraints.
Handles duplicate values efficiently by pre-calculating frequencies.
Cons
This approach's space complexity depends on the maximum possible value in the input arrays. If the numbers could be very large, it would require a large frequency array or a hash map, increasing space usage.
The implementation is slightly more complex than the brute-force approach.
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; }}class Solution {public: int numberOfPairs(vector<int> &nums1, vector<int> &nums2, int k) { int ans = 0; for (int x : nums1) { for (int y : nums2) { if (x % (y * k) == 0) { ++ans; } } } return ans; }};class Solution: def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int: return sum( x % (y * k) == 0 for x in nums1 for y in nums2)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.