Find the Number of Good Pairs I

Find the Number of Good Pairs I

What is this problem about?

In the Find the Number of Good Pairs I interview question, you are given two arrays, nums1 and nums2, and an integer k. A pair $(i, j)$ is called "good" if nums1[i] is divisible by nums2[j] * k. You need to return the total number of such good pairs.

Why is this asked in interviews?

Airbus and Google use this "Easy" question to test basic loop logic and divisibility checks. It evaluation whether you can correctly iterate through two datasets and apply a multi-factor condition. While simple, it’s a good test of a candidate's ability to implement a brute-force approach accurately before considering optimizations for larger datasets.

Algorithmic pattern used

This problem follows an Enumeration (Nested Loops) pattern.

1. Initialize a count = 0.
2. Iterate through every element $x$ in nums1.
3. Iterate through every element $y$ in nums2.
4. Check if x % (y * k) == 0.
5. If true, increment the count.

Example explanation

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

1. Check 12:
   • $12 \% (2 imes 1) = 0$. (Good pair!)
   • $12 \% (3 imes 1) = 0$. (Good pair!)
2. Check 6:
   • $6 \% (2 imes 1) = 0$. (Good pair!)
   • $6 \% (3 imes 1) = 0$. (Good pair!) Total good pairs = 4.

Common mistakes candidates make

• Incorrect Modulo: Using (x * k) % y instead of x % (y * k).
• Loop Boundaries: Off-by-one errors when iterating through the arrays.
• Initialization: Forgetting to reset or initialize the counter.

Interview preparation tip

For "Version I" of a problem, a brute-force $O(N imes M)$ solution is usually expected and sufficient given the small constraints. Always state the complexity of your solution to show you are aware of its performance.