Problem Description
Given two integer arrays nums1 and nums2 and a positive integer k, a pair (i, j) is called good if nums1[i] is divisible by (nums2[j] * k). The task is to return the total number of good pairs.
Key Insights
- The condition means that for a valid pair, nums1[i] % (nums2[j] * k) should equal 0.
- Instead of iterating over all possible pairs (which would be inefficient for large arrays), use frequency maps for both arrays.
- For each distinct number b in nums2, check all multiples of (b * k) present in nums1.
- Multiples can be generated iteratively, and their frequencies from nums1 can be used to determine the count of good pairs.
Space and Time Complexity
Time Complexity: O(U + (maxA / (b * k)) for each distinct b) where U is the number of unique elements in nums2 and maxA is the maximum value in nums1 (bounded by 10^6). In worst-case this is efficient enough. Space Complexity: O(n + m) for storing frequency counts.
Solution
We first build frequency maps for nums1 and nums2. For every distinct number in nums2, compute step = b * k. If step exceeds the maximum possible value in nums1, skip it. Otherwise, iterate through the multiples of step (i.e., step, 2step, 3step, …) up to 10^6 and add frequencyA[multiple] * frequencyB[b] to the answer. This way, we efficiently count all good pairs without checking each pair explicitly.