LeetCode 3164 - Find the Number of Good Pairs II

We are given two integer arrays, nums1 and nums2, along with a positive integer k. A pair of indices (i, j) is considered good if: In other words, nums1[i] must be divisible by nums2[j] k. The task is to count how many such index pairs exist.

leetcodemediumarrayhash-table

LeetCode Problem 3164

Difficulty: 🟡 Medium
Topics: Array, Hash Table

Solution

Problem Understanding

We are given two integer arrays, nums1 and nums2, along with a positive integer k.

A pair of indices (i, j) is considered good if:

$$nums1[i] \bmod (nums2[j] \times k) = 0$$

In other words, nums1[i] must be divisible by nums2[j] * k.

The task is to count how many such index pairs exist.

The arrays can each contain up to 10^5 elements, and values inside the arrays can be as large as 10^6. These constraints immediately rule out inefficient nested loop solutions in many cases, because checking every pair directly could require:

$$10^5 \times 10^5 = 10^{10}$$

operations, which is far too slow.

A key observation is that divisibility relationships are driven by factors and multiples. Instead of testing every pair individually, we should reorganize the problem around divisors.

Since k is always positive, we can safely divide elements of nums1 by k whenever divisible. If a value in nums1 is not divisible by k, then it can never form a valid pair, because:

$$nums2[j] \times k$$

must divide it exactly.

Important edge cases include:

  • Elements in nums1 not divisible by k, these can never contribute to the answer.
  • Duplicate values in nums2, because every occurrence contributes separately.
  • Very large repeated values, where frequency counting becomes important for efficiency.
  • Cases where no valid pairs exist.
  • Cases where every pair is valid.

The problem guarantees all numbers are positive, which simplifies divisor enumeration because we never need to handle zero or negative values.

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 and test:

$$nums1[i] % (nums2[j] \times k) == 0$$

If true, we increment the answer.

This approach is correct because it explicitly verifies the exact condition for every pair.

However, its time complexity is:

$$O(n \times m)$$

With both arrays potentially containing 10^5 elements, this becomes too slow.

Key Insight for the Optimal Solution

Suppose:

$$nums1[i] % (nums2[j] \times k) == 0$$

We can rewrite this as:

$$nums2[j] \mid \frac{nums1[i]}{k}$$

but only if nums1[i] is divisible by k.

So the problem becomes:

  1. Filter elements in nums1 that are divisible by k
  2. Divide them by k
  3. Count how many values in nums2 divide the resulting number

This transforms the problem into a divisor counting problem.

Instead of checking every nums2[j], we can:

  • Build a frequency map of nums2
  • Enumerate all divisors of each transformed value from nums1
  • Add frequencies of matching divisors

Since divisor enumeration takes approximately O(sqrt(x)), the solution becomes efficient enough.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n × m) O(1) Checks every pair directly
Optimal O(m + n × √M) O(m) Uses divisor enumeration and frequency counting

Here, M is the maximum value in nums1.

Algorithm Walkthrough

  1. Create a frequency map for all values in nums2.

We use a hash map because duplicates matter. If a value appears multiple times in nums2, every occurrence contributes separately to the final count. 2. Initialize the answer variable.

The result can become large, so we keep a running total using a sufficiently large integer type. 3. Iterate through every value in nums1.

For each number:

  • If it is not divisible by k, skip it immediately.
  • Otherwise, compute:

$$target = \frac{num}{k}$$

  1. Enumerate all divisors of target.

We loop from 1 to:

$$\sqrt{target}$$

If d divides target, then both:

$$d$$

and

$$\frac{target}{d}$$

are divisors.

  1. Check whether each divisor exists in nums2.

For every divisor found:

  • Add freq[d]
  • Add freq[target // d] if it is different from d
  1. Continue until all elements in nums1 are processed.
  2. Return the accumulated answer.

Why it works

After dividing a valid nums1[i] by k, we need to count how many values in nums2 divide the resulting number exactly.

Enumerating all divisors guarantees we consider every possible valid value from nums2. Using the frequency map ensures duplicates are counted correctly.

Because every valid pair corresponds exactly to one divisor relationship, the algorithm counts all good pairs without omission or duplication.

Python Solution

from collections import Counter
from math import isqrt
from typing import List

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

        total_pairs = 0

        for num in nums1:
            if num % k != 0:
                continue

            target = num // k

            for divisor in range(1, isqrt(target) + 1):
                if target % divisor != 0:
                    continue

                other_divisor = target // divisor

                total_pairs += freq.get(divisor, 0)

                if other_divisor != divisor:
                    total_pairs += freq.get(other_divisor, 0)

        return total_pairs

The implementation begins by building a frequency map using Counter. This allows constant time lookup for how many times a particular value appears in nums2.

We then iterate through every number in nums1. Any value not divisible by k is skipped immediately because it cannot possibly satisfy the divisibility condition.

For valid values, we compute target = num // k. The task now becomes finding all divisors of target.

The divisor enumeration uses the standard square root optimization. Whenever divisor divides target, both divisor and target // divisor are valid divisors.

We add the frequencies of these divisors from the hash map. When both divisors are the same, which happens for perfect squares, we only count it once.

Finally, the accumulated count is returned.

Go Solution

package main

import "math"

func numberOfPairs(nums1 []int, nums2 []int, k int) int64 {
	freq := make(map[int]int)

	for _, num := range nums2 {
		freq[num]++
	}

	var totalPairs int64 = 0

	for _, num := range nums1 {
		if num%k != 0 {
			continue
		}

		target := num / k
		limit := int(math.Sqrt(float64(target)))

		for divisor := 1; divisor <= limit; divisor++ {
			if target%divisor != 0 {
				continue
			}

			otherDivisor := target / divisor

			totalPairs += int64(freq[divisor])

			if otherDivisor != divisor {
				totalPairs += int64(freq[otherDivisor])
			}
		}
	}

	return totalPairs
}

The Go solution follows the same logic as the Python version.

A map[int]int is used for frequency counting. Since the total number of pairs can exceed the range of a 32 bit integer, the answer uses int64.

Go does not provide a built in integer square root function like Python's isqrt, so we use math.Sqrt and convert the result back to an integer.

The algorithm otherwise remains identical.

Worked Examples

Example 1

Input:

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

Frequency map for nums2:

Value Frequency
1 1
3 1
4 1

Processing nums1[0] = 1

target = 1 // 1 = 1

Divisors of 1:

Divisor Exists in nums2 Count Added
1 Yes 1

Running total:

1

Processing nums1[1] = 3

target = 3

Divisors:

Divisor Matching Value Count Added
1 1 1
3 3 1

Running total:

3

Processing nums1[2] = 4

target = 4

Divisors:

Divisor Matching Value Count Added
1 1 1
2 No 0
4 4 1

Final answer:

5

Example 2

Input:

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

Frequency map:

Value Frequency
2 1
4 1

Processing elements

nums1 Value Divisible by 3 target Valid Divisors in nums2 Pairs Added
1 No - - 0
2 No - - 0
4 No - - 0
12 Yes 4 2, 4 2

Final answer:

2

Complexity Analysis

Measure Complexity Explanation
Time O(m + n × √M) Frequency map construction plus divisor enumeration
Space O(m) Hash map storing frequencies of nums2

The frequency map requires linear space relative to the size of nums2.

For each value in nums1, we enumerate divisors up to its square root. Since values are at most 10^6, divisor enumeration is efficient enough for the problem constraints.

Test Cases

from typing import List

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        from collections import Counter
        from math import isqrt

        freq = Counter(nums2)

        total_pairs = 0

        for num in nums1:
            if num % k != 0:
                continue

            target = num // k

            for divisor in range(1, isqrt(target) + 1):
                if target % divisor == 0:
                    other_divisor = target // divisor

                    total_pairs += freq.get(divisor, 0)

                    if other_divisor != divisor:
                        total_pairs += freq.get(other_divisor, 0)

        return total_pairs

sol = Solution()

assert sol.numberOfPairs([1, 3, 4], [1, 3, 4], 1) == 5  # provided example 1

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

assert sol.numberOfPairs([10], [1, 2, 5], 1) == 3  # all divisors match

assert sol.numberOfPairs([5], [2, 4], 1) == 0  # no valid divisors

assert sol.numberOfPairs([12], [1, 2, 3, 4, 6, 12], 1) == 6  # many divisors

assert sol.numberOfPairs([8, 16], [2, 2, 4], 2) == 6  # duplicate nums2 values

assert sol.numberOfPairs([1], [1], 1) == 1  # smallest valid input

assert sol.numberOfPairs([999983], [1, 999983], 1) == 2  # large prime number

assert sol.numberOfPairs([1000000], [1, 10, 100, 1000], 10) == 4  # large values

assert sol.numberOfPairs([7, 11, 13], [2, 3, 5], 2) == 0  # none divisible by k
Test Why
[1,3,4], [1,3,4], k=1 Verifies provided example
[1,2,4,12], [2,4], k=3 Verifies filtering by k
[10], [1,2,5], k=1 Tests multiple matching divisors
[5], [2,4], k=1 Tests zero valid pairs
[12], [1,2,3,4,6,12], k=1 Tests many divisor matches
[8,16], [2,2,4], k=2 Verifies duplicate handling
[1], [1], k=1 Smallest valid input
[999983], [1,999983], k=1 Tests large prime values
[1000000], [1,10,100,1000], k=10 Tests large composite values
[7,11,13], [2,3,5], k=2 Tests skipping non divisible values

Edge Cases

One important edge case occurs when elements in nums1 are not divisible by k. These values can never form valid pairs because the divisor must include the factor k. A naive implementation might still attempt divisor enumeration, wasting time or producing incorrect results. The solution handles this safely with an immediate skip check:

if num % k != 0:
    continue

Another important case involves duplicate values in nums2. Since the problem counts index pairs rather than distinct values, duplicates must contribute multiple times. Using a frequency map ensures every occurrence is counted correctly.

Perfect squares are another common source of bugs during divisor enumeration. For example, the divisors of 16 include (4,4). A naive implementation might count the divisor 4 twice. The algorithm prevents double counting by checking:

if other_divisor != divisor:

This guarantees each divisor pair contributes correctly.