Problem Description

You have two integer arrays nums1 and nums2 with lengths n and m respectively. You also have a positive integer k.

A pair (i, j) is considered good if nums1[i] is divisible by nums2[j] * k, where 0 <= i <= n - 1 and 0 <= j <= m - 1.

Your task is to find and return the total number of good pairs.

For example, if nums1[i] = 12, nums2[j] = 3, and k = 2, then this would be a good pair because 12 is divisible by 3 * 2 = 6 (since 12 % 6 = 0).

The solution uses hash tables to optimize the counting process. First, it filters elements from nums1 that are divisible by k and stores their quotients (after dividing by k) in a counter. Then, for each unique value in nums2, it counts how many of its multiples appear in the processed nums1 values. The key insight is that if nums1[i] is divisible by nums2[j] * k, then nums1[i] / k must be divisible by nums2[j]. By iterating through multiples of each value in nums2 up to the maximum value in the processed nums1, the solution efficiently counts all good pairs.

Intuition

The key observation is that checking if nums1[i] is divisible by nums2[j] * k for every pair would result in O(n*m) time complexity, which could be inefficient for large arrays.

Let's think about the divisibility condition differently. If nums1[i] is divisible by nums2[j] * k, we can rewrite this as:

• nums1[i] % (nums2[j] * k) == 0
• This means nums1[i] / k must be divisible by nums2[j]

But wait - for nums1[i] to be divisible by nums2[j] * k, it must first be divisible by k itself. If nums1[i] is not divisible by k, it can never form a good pair with any element from nums2.

This leads us to our first optimization: we only need to consider elements in nums1 that are divisible by k. For these elements, we can work with nums1[i] / k instead of nums1[i].

Now, instead of checking divisibility for each pair individually, we can reverse our thinking. For each value x in nums2, we want to find how many values in our modified nums1 (after dividing by k) are divisible by x. These would be exactly the multiples of x: x, 2x, 3x, 4x, ...

By using hash tables to count occurrences and then iterating through multiples, we avoid redundant checks. For each unique value in nums2, we find all its multiples that exist in the processed nums1 array, multiply by their respective frequencies, and sum up the results.

This approach transforms the problem from checking all pairs to efficiently counting multiples using frequency maps, significantly improving the time complexity.

Solution Approach

The implementation uses hash tables and the enumerate multiples pattern to efficiently count good pairs.

Step 1: Build the first counter

cnt1 = Counter(x // k for x in nums1 if x % k == 0)

We iterate through nums1 and filter elements divisible by k. For each such element x, we store x // k in the counter cnt1. This preprocessing step ensures we only work with relevant elements and simplifies our divisibility check later.

Step 2: Early termination check

if not cnt1:
    return 0

If no elements in nums1 are divisible by k, there can be no good pairs, so we return 0 immediately.

Step 3: Build the second counter and find maximum

cnt2 = Counter(nums2)
mx = max(cnt1)

We count the frequency of each element in nums2 using cnt2. We also find the maximum key in cnt1, which represents the largest value we need to check when enumerating multiples.

Step 4: Enumerate multiples for each unique value in nums2

for x, v in cnt2.items():
    s = sum(cnt1[y] for y in range(x, mx + 1, x))
    ans += s * v

For each unique value x in nums2 with frequency v:

• We generate all multiples of x from x to mx using range(x, mx + 1, x). This gives us x, 2x, 3x, ... up to mx.
• For each multiple y, we check if it exists in cnt1 and sum up all occurrences: sum(cnt1[y] for y in range(x, mx + 1, x)).
• We multiply this sum s by the frequency v of x in nums2, since each occurrence of x in nums2 contributes to s good pairs.
• We accumulate the result in ans.

The algorithm leverages the fact that instead of checking divisibility for every pair, we can count how many times each multiple appears and use multiplication to get the total count, reducing time complexity significantly.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• nums1 = [12, 6, 8, 24]
• nums2 = [3, 2, 4]
• k = 2

Step 1: Filter nums1 and divide by k

We check which elements in nums1 are divisible by k = 2:

• 12 % 2 = 0 ✓ → 12 / 2 = 6
• 6 % 2 = 0 ✓ → 6 / 2 = 3
• 8 % 2 = 0 ✓ → 8 / 2 = 4
• 24 % 2 = 0 ✓ → 24 / 2 = 12

So cnt1 = {6: 1, 3: 1, 4: 1, 12: 1}

Step 2: Build counter for nums2 and find maximum

cnt2 = {3: 1, 2: 1, 4: 1} mx = max(cnt1) = 12

Step 3: Count good pairs by enumerating multiples

For each unique value in nums2:

• For x = 3 (frequency = 1):

  • Multiples of 3 up to 12: 3, 6, 9, 12
  • Check which exist in cnt1:
    • 3 exists → count = 1
    • 6 exists → count = 1
    • 9 doesn't exist → count = 0
    • 12 exists → count = 1
  • Sum = 1 + 1 + 0 + 1 = 3
  • Contribution = 3 × 1 = 3 good pairs

• For x = 2 (frequency = 1):

  • Multiples of 2 up to 12: 2, 4, 6, 8, 10, 12
  • Check which exist in cnt1:
    • 2 doesn't exist → count = 0
    • 4 exists → count = 1
    • 6 exists → count = 1
    • 8 doesn't exist → count = 0
    • 10 doesn't exist → count = 0
    • 12 exists → count = 1
  • Sum = 0 + 1 + 1 + 0 + 0 + 1 = 3
  • Contribution = 3 × 1 = 3 good pairs

• For x = 4 (frequency = 1):

  • Multiples of 4 up to 12: 4, 8, 12
  • Check which exist in cnt1:
    • 4 exists → count = 1
    • 8 doesn't exist → count = 0
    • 12 exists → count = 1
  • Sum = 1 + 0 + 1 = 2
  • Contribution = 2 × 1 = 2 good pairs

Total good pairs = 3 + 3 + 2 = 8

Verification of actual good pairs:

1. (0,0): 12 % (3×2) = 12 % 6 = 0 ✓
2. (0,1): 12 % (2×2) = 12 % 4 = 0 ✓
3. (0,2): 12 % (4×2) = 12 % 8 = 4 ✗
4. (1,0): 6 % (3×2) = 6 % 6 = 0 ✓
5. (1,1): 6 % (2×2) = 6 % 4 = 2 ✗
6. (1,2): 6 % (4×2) = 6 % 8 = 6 ✗
7. (2,0): 8 % (3×2) = 8 % 6 = 2 ✗
8. (2,1): 8 % (2×2) = 8 % 4 = 0 ✓
9. (2,2): 8 % (4×2) = 8 % 8 = 0 ✓
10. (3,0): 24 % (3×2) = 24 % 6 = 0 ✓
11. (3,1): 24 % (2×2) = 24 % 4 = 0 ✓
12. (3,2): 24 % (4×2) = 24 % 8 = 0 ✓

Count of ✓ = 8, which matches our calculated result!

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m + (M/k) × √(M/k))

Breaking down the time complexity:

• Creating cnt1: O(n) - iterates through nums1 once, with O(1) operations for division and modulo checks
• Creating cnt2: O(m) - iterates through nums2 once
• Finding mx = max(cnt1): O(n) in worst case when all elements in nums1 are divisible by k
• The nested loop structure:
  • Outer loop iterates through each unique value in cnt2: at most O(m) iterations
  • Inner loop (the range operation) for each x iterates from x to mx with step x, which gives mx/x iterations
  • The sum of all inner loop iterations across all x values is bounded by the sum of divisors of all numbers up to mx
  • For a number mx = M/k, the sum of mx/1 + mx/2 + ... + mx/mx is O((M/k) × log(M/k)) using the harmonic series approximation

However, upon closer inspection, the reference answer suggests O(n + m + (M/k) × log m). This could be interpreted as considering that the number of unique values in cnt2 is at most m, and for each position up to M/k, we might need to check O(log m) divisors on average.

Space Complexity: O(n + m)

Breaking down the space complexity:

• cnt1: O(n) in worst case when all elements in nums1 are divisible by k and unique after division
• cnt2: O(m) in worst case when all elements in nums2 are unique
• Other variables (ans, mx, s, x, v): O(1)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Check Divisibility by k First

A common mistake is attempting to process all elements in nums1 without first filtering for divisibility by k. This leads to incorrect results or runtime errors.

Incorrect approach:

# Wrong: Dividing without checking divisibility first
frequency_nums1_divided = Counter(num // k for num in nums1)

Why it fails: If nums1[i] is not divisible by k, then the pair cannot be good regardless of nums2[j]. Including num // k when num % k != 0 will lead to counting invalid pairs.

Correct approach:

# Filter elements divisible by k before dividing
frequency_nums1_divided = Counter(num // k for num in nums1 if num % k == 0)

2. Integer Division vs Float Division Confusion

Using float division (/) instead of integer division (//) can cause issues with the Counter and subsequent calculations.

Incorrect approach:

# Wrong: Using float division
frequency_nums1_divided = Counter(num / k for num in nums1 if num % k == 0)

Why it fails: This creates float keys in the Counter (e.g., 6.0 instead of 6), which won't match properly when checking multiples using integer ranges.

Correct approach:

# Use integer division
frequency_nums1_divided = Counter(num // k for num in nums1 if num % k == 0)

3. Off-by-One Error in Range

When enumerating multiples, forgetting to include max_value itself in the range is a subtle but critical error.

Incorrect approach:

# Wrong: Excludes max_value
for multiple in range(nums2_value, max_value, nums2_value)

Why it fails: If max_value itself is a multiple of nums2_value, it won't be counted, leading to missing valid pairs.

Correct approach:

# Include max_value by adding 1
for multiple in range(nums2_value, max_value + 1, nums2_value)

4. Not Handling Empty Counter Case

Failing to check if frequency_nums1_divided is empty before finding the maximum can cause a runtime error.

Incorrect approach:

# Wrong: Assumes counter is non-empty
frequency_nums1_divided = Counter(num // k for num in nums1 if num % k == 0)
max_value = max(frequency_nums1_divided)  # ValueError if empty

Why it fails: If no elements in nums1 are divisible by k, the Counter is empty, and max() on an empty sequence raises a ValueError.

Correct approach:

frequency_nums1_divided = Counter(num // k for num in nums1 if num % k == 0)
if not frequency_nums1_divided:
    return 0
max_value = max(frequency_nums1_divided)

5. Incorrect Multiplication of Counts

A subtle error is forgetting to multiply by the frequency of values in nums2, treating each unique value as appearing only once.

Incorrect approach:

# Wrong: Not accounting for frequency in nums2
for nums2_value in set(nums2):  # Using set loses frequency information
    multiples_count = sum(
        frequency_nums1_divided[multiple] 
        for multiple in range(nums2_value, max_value + 1, nums2_value)
    )
    total_pairs += multiples_count  # Missing multiplication by frequency

Why it fails: Each occurrence of a value in nums2 can form pairs with all valid elements in nums1, so we need to multiply by its frequency.

Correct approach:

frequency_nums2 = Counter(nums2)
for nums2_value, nums2_count in frequency_nums2.items():
    multiples_count = sum(
        frequency_nums1_divided[multiple] 
        for multiple in range(nums2_value, max_value + 1, nums2_value)
    )
    total_pairs += multiples_count * nums2_count