#3162

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find the Number of Good Pairs I

Count all good pairs where an element in nums1 is divisible by a scaled element in nums2 using efficient array scanning.

array hash table

Problem Statement

You are given two integer arrays nums1 and nums2 of sizes n and m, along with a positive integer k. A pair of indices (i, j) is defined as good if nums1[i] is divisible by nums2[j] multiplied by k. Your task is to determine the total number of such good pairs across both arrays.

Return a single integer representing the number of good pairs. Consider all valid index pairs where 0 <= i < n and 0 <= j < m. Constraints are small, allowing a straightforward check of every pair while leveraging hash lookups to optimize repeated value checks in nums2.

Examples

Example 1

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

Output: 5

Example 2

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

Output: 2

The 2 good pairs are (3, 0) and (3, 1) .

Constraints

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

Solution Approach

Brute-force Array Scan

Iterate through each element in nums1 and for each, iterate through nums2. Check if nums1[i] is divisible by nums2[j] * k and increment a counter. This direct approach works due to the small constraints of n and m.

Hash Table for nums2 Frequency

Use a hash table to store counts of each number in nums2. For each nums1[i], calculate the required divisor and check its frequency in the hash. Multiply counts appropriately to sum all good pairs efficiently.

Combine Scanning with Hash Lookup

Merge the brute-force scan with hash table lookups: scan nums1 once and use the hash table to quickly find how many nums2[j] satisfy divisibility by k. This reduces redundant checks and keeps runtime manageable.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * m) in the naive scan, but using hash lookup for nums2 reduces repeated divisor checks. Space complexity is O(m) for the hash table storing nums2 counts.

What Interviewers Usually Probe

Ask about using hash tables to optimize repeated divisor checks in nums2.
Check if the candidate considers array scanning versus nested loops for efficiency.
Probe understanding of how small constraints affect the choice of brute-force or optimized approach.

Common Pitfalls or Variants

Common pitfalls

Forgetting to multiply nums2[j] by k before checking divisibility.
Double-counting pairs if using hash table incorrectly.
Assuming sorted arrays when order does not matter, leading to wrong indexing.

Follow-up variants

Consider counting good pairs with nums1[i] divisible by nums2[j] + k instead of multiplied.
Modify the problem to handle large arrays requiring more optimized divisor counting strategies.
Count good pairs where nums1[i] modulo nums2[j] equals k, changing the divisibility condition.

FAQ

What defines a good pair in Find the Number of Good Pairs I?

A good pair is any indices (i, j) where nums1[i] is divisible by nums2[j] multiplied by k.

Is a hash table necessary for small input arrays?

Not strictly, but using a hash table reduces redundant divisor checks and improves clarity.

Can I assume nums1 and nums2 are sorted?

No, the arrays can be in any order; divisibility is independent of sorting.

How do constraints affect the approach?

Small constraints allow nested loops, while hash tables optimize repeated checks without increasing complexity.

What is the main pattern used in this problem?

The primary pattern is array scanning combined with hash lookup to efficiently count good pairs.

terminal

Solution

Solution 1: Brute Force Enumeration

We directly enumerate all digit pairs $(x, y)$ and check whether $x \bmod (y \times k) = 0$. If it satisfies the condition, increment the answer by one.

1

2

3

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        return sum(x % (y * k) == 0 for x in nums1 for y in nums2)

Solution 2: Hash Table + Enumerate Multiples

We use a hash table `cnt1` to record the occurrence times of each number divided by $k$ in array `nums1`, and a hash table `cnt2` to record the occurrence times of each number in array `nums2`.

1

2

3

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        return sum(x % (y * k) == 0 for x in nums1 for y in nums2)

Continue Practicing

#3160 find the number of distinct colors among the balls #3164 find the number of good pairs ii #3159 find occurrences of an element in an array