Find the Number of Good Pairs I

Difficulty: Easy | Acceptance: 86.40% | Paid: No Topics: Array, Hash Table

You are given two 0-indexed integer arrays nums1 and nums2 of lengths n and m respectively, and an integer k. A pair (i, j) is called good if nums1[i] is divisible by nums2[j] * k. Return the number of good pairs.

• Examples
• Constraints
• Brute Force
• Hash Map Optimization
• Divisor Enumeration

Examples

Input: nums1 = [1,2,3,4], nums2 = [1,2,3], k = 1
Output: 7
Explanation: 
The 7 good pairs are:
(0,0): 1 is divisible by 1 * 1
(1,0): 2 is divisible by 1 * 1
(1,1): 2 is divisible by 2 * 1
(2,0): 3 is divisible by 1 * 1
(2,2): 3 is divisible by 3 * 1
(3,0): 4 is divisible by 1 * 1
(3,1): 4 is divisible by 2 * 1

Input: nums1 = [1,2,3,4], nums2 = [1,2,3], k = 2
Output: 3
Explanation:
The 3 good pairs are:
(1,0): 2 is divisible by 1 * 2
(3,0): 4 is divisible by 1 * 2
(3,1): 4 is divisible by 2 * 2

Constraints

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

Brute Force

Intuition Since the constraints are very small (arrays of length at most 50), we can simply check every possible pair (i, j) to see if it satisfies the condition.

Steps

• Initialize a counter to 0.
• Iterate through each element num1 in nums1.
• For each num1, iterate through each element num2 in nums2.
• Check if num1 % (num2 * k) == 0.
• If the condition is true, increment the counter.
• Return the counter.

from typing import List

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        count = 0
        for n1 in nums1:
            for n2 in nums2:
                if n1 % (n2 * k) == 0:
                    count += 1
        return count

Complexity

• Time: O(n * m), where n and m are the lengths of the arrays.
• Space: O(1)
• Notes: This is the most straightforward approach and is efficient enough given the constraints.

Hash Map Optimization

Intuition If nums2 contains many duplicate values, we can optimize by counting the frequency of each number in nums2. Then, for each number in nums1, we only check against the unique values in nums2, multiplying the result by the frequency of the valid nums2 value.

Steps

• Create a frequency map (hash table) for elements in nums2.
• Initialize a counter to 0.
• Iterate through each element num1 in nums1.
• For each unique value num2 in the frequency map:
  • Check if num1 % (num2 * k) == 0.
  • If true, add freq[num2] to the counter.
• Return the counter.

from typing import List
from collections import Counter

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        freq = Counter(nums2)
        count = 0
        for n1 in nums1:
            for n2, cnt in freq.items():
                if n1 % (n2 * k) == 0:
                    count += cnt
        return count

Complexity

• Time: O(n * m) in the worst case (if all elements in nums2 are unique), but faster with duplicates.
• Space: O(m) to store the frequency map.
• Notes: Reduces redundant calculations when nums2 has duplicates.

Divisor Enumeration

Intuition For a pair to be good, nums2[j] * k must be a divisor of nums1[i]. Instead of iterating through nums2, we can find all divisors of nums1[i] and check if any divisor d satisfies d % k == 0 and d / k exists in nums2. This is efficient when the values in the array are small.

Steps

• Create a frequency map for nums2.
• Initialize a counter to 0.
• Iterate through each element num1 in nums1.
• Find all divisors d of num1 (from 1 to sqrt(num1)).
• For each divisor d:
  • If d % k == 0, check if d / k is in the frequency map. If so, add its frequency to the count.
  • Check the complementary divisor num1 / d (if different from d) and repeat the check.
• Return the counter.

from typing import List
from collections import Counter

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        freq = Counter(nums2)
        count = 0
        for n1 in nums1:
            for d in range(1, int(n1**0.5) + 1):
                if n1 % d == 0:
                    if d % k == 0:
                        count += freq.get(d // k, 0)
                    other = n1 // d
                    if other != d and other % k == 0:
                        count += freq.get(other // k, 0)
        return count

Complexity

• Time: O(n * sqrt(V)), where V is the maximum value in nums1.
• Space: O(m) to store the frequency map.
• Notes: This approach is very efficient when the array values are small, as finding divisors is fast.