Find the Number of Good Pairs II

Find the Number of Good Pairs II

What is this problem about?

This is the "Medium" version of the previous problem. In Find the Number of Good Pairs II, the arrays nums1 and nums2 can be much larger ($10^5$), making an $O(N imes M)$ solution too slow. You still need to find pairs $(i, j)$ where nums1[i] is divisible by nums2[j] * k.

Why is this asked in interviews?

Companies like Amazon and Bloomberg use this to test your knowledge of Number Theory interview patterns and Frequency Maps. It evaluations whether you can optimize a divisibility check by looking at factors. Instead of checking every pair, you can count how many multiples of $y imes k$ exist in the first array.

Algorithmic pattern used

This problem uses Frequency Counting and Multiples Enumeration.

1. Pre-calculate the frequencies of all numbers in nums1.
2. For each unique number $y$ in nums2:
   • Let target = y * k.
   • Iterate through all multiples of target ($target, 2 imes target, 3 imes target, \dots$) up to the maximum value in nums1.
   • For each multiple, add its frequency from nums1 to your total count.
3. This is efficient because the sum of $1/x$ (Harmonic Series) results in $O(MaxVal \log MaxVal)$ complexity.

Example explanation

nums1 = [12, 6, 12], nums2 = [3], k = 1.

1. Freqs of nums1: {12: 2, 6: 1}.
2. Check $y=3$: target = 3 imes 1 = 3.
3. Multiples of 3:
   • 3: freq 0.
   • 6: freq 1.
   • 9: freq 0.
   • 12: freq 2. Total = $1 + 2 = 3$.

Common mistakes candidates make

• Using Brute Force: Attempting the $O(N imes M)$ approach which times out.
• Redundant Calculations: Not using a frequency map for nums2, which would cause you to re-calculate multiples for the same $y$.
• Max Value Error: Not correctly identifying the upper bound for the multiples loop.

Interview preparation tip

When a problem involves "divisibility" across large arrays, think about "counting factors" or "iterating over multiples." This change in perspective (from pairs to factors) is a key optimization for many Array interview patterns.