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 when nums1[i] can be evenly divided by the product nums2[j] * k. Here, i is a valid index for nums1 (ranging from 0 to n - 1) and j is a valid index for nums2 (ranging from 0 to m - 1).

In other words, a pair (i, j) is good if nums1[i] % (nums2[j] * k) == 0.

Your task is to count and return the total number of good pairs across all possible combinations of indices from both arrays.

For example, if nums1 = [12, 24], nums2 = [3, 4], and k = 2:

• Pair (0, 0): Check if 12 % (3 * 2) == 0 → 12 % 6 == 0 → True (good pair)
• Pair (0, 1): Check if 12 % (4 * 2) == 0 → 12 % 8 == 0 → False (not good)
• Pair (1, 0): Check if 24 % (3 * 2) == 0 → 24 % 6 == 0 → True (good pair)
• Pair (1, 1): Check if 24 % (4 * 2) == 0 → 24 % 8 == 0 → True (good pair)

The total number of good pairs would be 3.

Intuition

The problem asks us to find pairs where one number is divisible by another number multiplied by k. This is fundamentally a divisibility checking problem.

Since we need to check every possible pair between the two arrays, the most straightforward approach is to examine each element from nums1 with each element from nums2. This naturally leads us to think about nested loops or nested iterations.

For each element x in nums1, we need to check it against every element y in nums2 to see if x is divisible by y * k. The divisibility check can be done using the modulo operator: if x % (y * k) == 0, then x is divisible by y * k.

The brute force approach makes sense here because:

1. We must examine all possible pairs to ensure we don't miss any good pairs
2. Each pair requires a simple arithmetic check (multiplication and modulo operation)
3. There's no apparent pattern or mathematical property that would allow us to skip certain pairs without checking

The solution can be elegantly expressed using a generator expression with two iterations - one over nums1 and one over nums2. For each combination, we perform the divisibility check and count how many pairs satisfy the condition. This gives us a concise one-liner that directly translates our intuition into code: iterate through all pairs, check the condition, and count the successes.

Solution Approach

The solution uses a brute force enumeration approach to check all possible pairs between the two arrays.

Implementation Steps:

1. Iterate through all pairs: We use nested iteration to generate all possible pairs (x, y) where x comes from nums1 and y comes from nums2.

2. Check divisibility condition: For each pair, we check if x % (y * k) == 0. This tells us whether x is divisible by the product of y and k.

3. Count valid pairs: We use Python's sum() function with a generator expression to count how many pairs satisfy the condition. Each True value from the condition check contributes 1 to the sum, while False contributes 0.

The one-liner implementation:

return sum(x % (y * k) == 0 for x in nums1 for y in nums2)

This expression:

• Uses for x in nums1 to iterate through each element in the first array
• Uses for y in nums2 to iterate through each element in the second array (nested)
• Evaluates x % (y * k) == 0 for each pair, producing a boolean value
• The sum() function counts the True values (treating True as 1 and False as 0)

Time Complexity: O(n * m) where n is the length of nums1 and m is the length of nums2, since we check every possible pair.

Space Complexity: O(1) as we only use a constant amount of extra space for the counting operation (the generator expression doesn't create an intermediate list).

Example Walkthrough

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

Given:

• nums1 = [10, 20, 30]
• nums2 = [2, 5]
• k = 2

Step-by-step process:

We'll check every possible pair (i, j) to see if nums1[i] % (nums2[j] * k) == 0.

Iteration 1: x = 10 (from nums1)

• Pair with y = 2: Check 10 % (2 * 2) = 10 % 4 = 2 → Not divisible → Not a good pair
• Pair with y = 5: Check 10 % (5 * 2) = 10 % 10 = 0 → Divisible → Good pair! ✓

Iteration 2: x = 20 (from nums1)

• Pair with y = 2: Check 20 % (2 * 2) = 20 % 4 = 0 → Divisible → Good pair! ✓
• Pair with y = 5: Check 20 % (5 * 2) = 20 % 10 = 0 → Divisible → Good pair! ✓

Iteration 3: x = 30 (from nums1)

• Pair with y = 2: Check 30 % (2 * 2) = 30 % 4 = 2 → Not divisible → Not a good pair
• Pair with y = 5: Check 30 % (5 * 2) = 30 % 10 = 0 → Divisible → Good pair! ✓

Summary of pairs checked:

Total good pairs: 4

The solution sum(x % (y * k) == 0 for x in nums1 for y in nums2) would generate these exact checks in order, evaluating to False + True + True + True + False + True = 4.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the length of nums1 and n is the length of nums2. This is because the code uses a nested loop structure with a generator expression - for each element x in nums1, it iterates through every element y in nums2, performing a constant-time modulo operation x % (y * k) == 0 for each pair. Therefore, the total number of operations is m × n.

The space complexity is O(1). The generator expression doesn't create any intermediate data structures and only uses a constant amount of extra space for the loop variables x and y, and for accumulating the sum. The sum() function processes the generator expression iteratively without storing all results in memory.

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

Common Pitfalls

1. Integer Overflow with Large Values

When computing num2 * k, the multiplication could potentially overflow if both num2 and k are large integers. While Python handles arbitrary precision integers automatically, in other languages or when optimizing, this could cause incorrect results.

Example Issue:

# If num2 = 10^9 and k = 10^9, their product is 10^18
# In languages with fixed integer sizes, this would overflow

Solution: Check if the product would exceed num1 before performing the modulo operation:

for num1 in nums1:
    for num2 in nums2:
        # Avoid unnecessary computation if num2 * k > num1
        if num2 <= num1 // k:  # Prevents overflow and improves efficiency
            if num1 % (num2 * k) == 0:
                count += 1

2. Division by Zero

If any element in nums2 is zero or if k is zero, the expression num1 % (num2 * k) would attempt modulo by zero, causing a runtime error.

Solution: Add validation or handle zero cases explicitly:

def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
    # Handle edge case where k is 0
    if k == 0:
        return 0
  
    count = 0
    for num1 in nums1:
        for num2 in nums2:
            # Skip if num2 is 0 to avoid modulo by zero
            if num2 == 0:
                continue
            if num1 % (num2 * k) == 0:
                count += 1
  
    return count

3. Performance Degradation with Large Arrays

The O(n*m) time complexity becomes problematic when both arrays are large (e.g., 10^5 elements each), resulting in 10^10 operations.

Solution: For better performance with large inputs, use factorization-based optimization:

def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
    from collections import Counter
  
    # Count occurrences of each value in nums2
    nums2_count = Counter(nums2)
    count = 0
  
    for num1 in nums1:
        # Only check divisors of num1/k if num1 is divisible by k
        if num1 % k == 0:
            quotient = num1 // k
            # Find all divisors of quotient that appear in nums2
            for i in range(1, int(quotient**0.5) + 1):
                if quotient % i == 0:
                    # i is a divisor
                    if i in nums2_count:
                        count += nums2_count[i]
                    # quotient/i is also a divisor (if different from i)
                    if i != quotient // i and quotient // i in nums2_count:
                        count += nums2_count[quotient // i]
  
    return count