LeetCode 3162 - Find the Number of Good Pairs I

LeetCode Problem 3162

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

Problem Understanding

The problem gives us two integer arrays, nums1 and nums2, along with a positive integer k. We need to count how many index pairs (i, j) satisfy the following condition:

nums1[i] is divisible by nums2[j] * k

In mathematical terms, a pair is considered good if:

nums1[i] % (nums2[j] * k) == 0

The task is not asking us to return the pairs themselves. Instead, we only need the total number of valid pairs.

The arrays can have different sizes, and every element is positive. Since divisibility is involved, we must carefully compute the product nums2[j] * k before checking whether it divides nums1[i].

The constraints are very small:

• 1 <= n, m <= 50
• 1 <= nums1[i], nums2[j] <= 50
• 1 <= k <= 50

These constraints tell us several important things:

• The total number of possible pairs is at most 50 * 50 = 2500.
• Even a straightforward nested loop solution is completely acceptable.
• There is no risk of integer overflow in Python or Go because the largest multiplication is 50 * 50 = 2500.

There are also several edge cases worth identifying early:

• Some products nums2[j] * k may be larger than elements in nums1, making divisibility impossible.
• Duplicate values in either array should each count separately because the problem counts index pairs, not unique values.
• When k is large, many pairs may become invalid because the divisor becomes larger.
• Since all values are positive, we never need to worry about division by zero.

Approaches

Brute Force Approach

The most direct solution is to check every possible pair (i, j).

For each element in nums1, we iterate through every element in nums2. We compute:

divisor = nums2[j] * k

Then we check whether:

nums1[i] % divisor == 0

If the condition is true, we increment our answer counter.

This approach is correct because it explicitly verifies the condition for every pair. Since every possible pair is examined exactly once, no valid pair is missed and no invalid pair is counted.

Although brute force is often considered inefficient, the constraints here are extremely small. At most, we perform 2500 divisibility checks, which is trivial.

Key Insight

The key observation is that the problem fundamentally asks us to test divisibility for every pair. Because the constraints are so small, there is no need for advanced optimization techniques such as frequency maps, divisor enumeration, or preprocessing.

In many problems involving pair counting, brute force would be too slow. Here, however, the input size is intentionally limited, so the simplest approach is already optimal enough.

This is an important lesson in algorithm design: the best solution depends on the constraints. A mathematically sophisticated solution is unnecessary when a straightforward approach already runs comfortably within limits.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(1)	Check every possible pair directly
Optimal	O(n × m)	O(1)	Same as brute force because constraints are very small

Algorithm Walkthrough

1. Initialize a variable count to store the number of good pairs.
2. Iterate through every value num1 in nums1.
3. For each num1, iterate through every value num2 in nums2.
4. Compute the divisor:

divisor = num2 * k

This is necessary because the condition depends on the product of nums2[j] and k, not just nums2[j]. 5. Check whether num1 is divisible by divisor:

num1 % divisor == 0

6. If the condition is true, increment count.
7. After all pairs have been processed, return count.

Why it works

The algorithm works because it directly implements the definition of a good pair from the problem statement. Every pair (i, j) is examined exactly once. If the divisibility condition holds, the pair is counted. Otherwise, it is ignored. Since no pair is skipped or double-counted, the final result is correct.

Python Solution

from typing import List

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        count = 0

        for num1 in nums1:
            for num2 in nums2:
                divisor = num2 * k

                if num1 % divisor == 0:
                    count += 1

        return count

The implementation follows the algorithm exactly.

The variable count stores the total number of valid pairs discovered so far.

The outer loop iterates through each value in nums1, while the inner loop iterates through each value in nums2. For every combination, we compute divisor = num2 * k.

The divisibility check uses the modulo operator. If the remainder is zero, then num1 is divisible by the divisor, meaning the pair is good.

Finally, the method returns the accumulated count.

Go Solution

func numberOfPairs(nums1 []int, nums2 []int, k int) int {
    count := 0

    for _, num1 := range nums1 {
        for _, num2 := range nums2 {
            divisor := num2 * k

            if num1%divisor == 0 {
                count++
            }
        }
    }

    return count
}

The Go implementation is nearly identical to the Python version.

Go uses range loops to iterate through slices. The modulo operation behaves the same way as in Python for positive integers.

There are no special concerns about integer overflow because the constraints are very small. Both empty and nil slices are handled naturally by Go loops, although the problem guarantees arrays have at least one element.

Worked Examples

Example 1

Input:

nums1 = [1, 3, 4]
nums2 = [1, 3, 4]
k = 1

Since k = 1, the divisors are simply the values from nums2.

num1	num2	divisor	num1 % divisor	Good Pair?	Count
1	1	1	0	Yes	1
1	3	3	1	No	1
1	4	4	1	No	1
3	1	1	0	Yes	2
3	3	3	0	Yes	3
3	4	4	3	No	3
4	1	1	0	Yes	4
4	3	3	1	No	4
4	4	4	0	Yes	5

Final answer:

5

Example 2

Input:

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

Now the divisors become:

2 * 3 = 6
4 * 3 = 12

num1	num2	divisor	num1 % divisor	Good Pair?	Count
1	2	6	1	No	0
1	4	12	1	No	0
2	2	6	2	No	0
2	4	12	2	No	0
4	2	6	4	No	0
4	4	12	4	No	0
12	2	6	0	Yes	1
12	4	12	0	Yes	2

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × m)	Every pair between the two arrays is checked once
Space	O(1)	Only a few variables are used

The time complexity comes from the nested loops. If n is the size of nums1 and m is the size of nums2, then we perform exactly n * m divisibility checks.

The space complexity is constant because the algorithm does not allocate any extra data structures proportional to the input size.

Test Cases

solution = Solution()

# Provided example 1
assert solution.numberOfPairs([1, 3, 4], [1, 3, 4], 1) == 5

# Provided example 2
assert solution.numberOfPairs([1, 2, 4, 12], [2, 4], 3) == 2

# Single element arrays, divisible
assert solution.numberOfPairs([12], [3], 2) == 1

# Single element arrays, not divisible
assert solution.numberOfPairs([10], [3], 2) == 0

# All pairs valid
assert solution.numberOfPairs([8, 16], [1, 2], 1) == 4

# No valid pairs
assert solution.numberOfPairs([5, 7], [2, 4], 3) == 0

# Duplicate values should count separately
assert solution.numberOfPairs([6, 6], [1, 1], 2) == 4

# Large k reduces valid pairs
assert solution.numberOfPairs([50, 100], [5, 10], 10) == 2

# Divisor larger than num1
assert solution.numberOfPairs([3], [10], 5) == 0

# Mixed divisibility cases
assert solution.numberOfPairs([24, 36, 48], [2, 3, 4], 2) == 8

Test	Why
[1,3,4], [1,3,4], k=1	Validates the first example
[1,2,4,12], [2,4], k=3	Validates the second example
Single divisible pair	Tests the smallest successful case
Single non-divisible pair	Tests the smallest failing case
All pairs valid	Ensures counting logic works correctly
No valid pairs	Ensures algorithm returns zero correctly
Duplicate values	Confirms index pairs are counted separately
Large k	Tests cases where multiplication changes divisibility
Divisor larger than value	Ensures modulo logic behaves correctly
Mixed divisibility	Tests a more complex combination of outcomes

Edge Cases

One important edge case occurs when nums2[j] * k is larger than nums1[i]. In such cases, divisibility is impossible unless the numbers are equal. A careless implementation might incorrectly assume smaller values always divide larger ones. This implementation safely uses the modulo operation directly, which correctly handles all such cases.

Another important case involves duplicate values. The problem counts index pairs, not unique numeric pairs. For example, if both arrays contain repeated elements, every valid index combination must be counted separately. The nested loop implementation naturally handles this because it processes every pair independently.

A third edge case appears when k is large. Multiplying nums2[j] by k can significantly change the divisor and invalidate pairs that would otherwise work. Some implementations may mistakenly check divisibility using only nums2[j]. This solution explicitly computes num2 * k before every divisibility check, ensuring correctness.

A final edge case involves the smallest possible inputs, where both arrays contain exactly one element. These cases are useful for validating loop boundaries and ensuring there are no off-by-one errors. Since the algorithm uses straightforward iteration over the arrays, it handles minimal inputs correctly without requiring any special logic.