LeetCode 2183 - Count Array Pairs Divisible by K

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Math, Counting, Number Theory

Solution

Problem Understanding

The problem gives us an integer array nums and an integer k. We must count how many index pairs (i, j) satisfy two conditions:

i < j
nums[i] * nums[j] is divisible by k

In other words, for every pair of distinct elements in the array, we check whether their product contains all the prime factors needed to divide evenly by k.

The input size is large:

nums.length can be up to 10^5
nums[i] and k can also be up to 10^5

These constraints immediately tell us that checking every pair directly will likely be too slow. A quadratic algorithm would require up to about 10^10 pair checks in the worst case, which is far beyond acceptable limits.

The important mathematical observation is that divisibility by k depends only on how each number contributes factors toward k. We do not need the full product value, we only need enough information to determine whether the combined factors of two numbers cover all factors of k.

Some important edge cases include:

k = 1, where every pair is valid because every integer is divisible by 1.
Arrays where no pair can satisfy the condition.
Arrays where every pair satisfies the condition.
Repeated values, which can create many valid combinations.
Large arrays with large values, where efficiency becomes critical.

The problem guarantees that all numbers are positive integers, so we do not need to worry about negative numbers or zero.

Approaches

Brute Force Approach

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

For each pair:

Compute nums[i] * nums[j]
Check whether the product is divisible by k
If yes, increment the answer

This works because it explicitly tests the exact condition required by the problem.

However, the time complexity is too large. With n = 10^5, the number of pairs is approximately:

$$\frac{n(n-1)}{2}$$

which is about 5 * 10^9 comparisons in the worst case. This is far too slow.

Key Insight for the Optimal Approach

Instead of looking at full products, we can focus on greatest common divisors.

For each number x, compute:

$$g = \gcd(x, k)$$

This tells us which factors of k are already contributed by x.

Suppose we already processed another number with gcd value g2.

We want:

$$x \cdot y \equiv 0 \pmod{k}$$

This is equivalent to:

$$k \mid (x \cdot y)$$

Using gcd properties, we only need to check whether:

$$g \cdot g2$$

contains all factors of k, meaning:

$$(g \cdot g2) \bmod k = 0$$

This dramatically reduces the problem size because gcd values are limited to divisors of k, not arbitrary integers.

We can store counts of previously seen gcd values in a hash map and efficiently count valid matches.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every pair directly
Optimal	O(n × d)	O(d)	Uses gcd grouping and divisor compatibility

Here, d is the number of distinct gcd values encountered, which is bounded by the number of divisors of k.

Algorithm Walkthrough

Initialize a hash map called gcd_count.

This map stores how many previous numbers produced each gcd value with k. 2. Initialize the answer variable to 0.

This will accumulate the number of valid pairs. 3. Iterate through each number num in nums.

For the current number, compute:

$$current_gcd = \gcd(num, k)$$

This represents the factors of k contributed by num. 4. Compare the current gcd against all previously seen gcd values.

For every stored gcd value previous_gcd, check whether:

$$(current_gcd \times previous_gcd) \bmod k = 0$$

If true, then any number with gcd previous_gcd forms a valid pair with the current number. 5. Add the count of matching gcd values to the answer.

Since the hash map stores frequencies, we can add all matching pairs at once. 6. Insert the current gcd into the hash map.

Increment its frequency so future numbers can pair with it. 7. Continue until all numbers are processed. 8. Return the accumulated answer.

Why it works

For any number x, the value gcd(x, k) captures exactly which factors of k are present in x.

If two numbers have gcd values g1 and g2, then their product is divisible by k exactly when the combined factors from g1 and g2 cover all prime factors of k.

Therefore, checking:

$$(g1 \times g2) \bmod k = 0$$

correctly determines whether the original product is divisible by k.

Because every pair is counted exactly once when processing the later element, the algorithm produces the correct answer.

Python Solution

from typing import List
from collections import defaultdict
from math import gcd

class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        gcd_count = defaultdict(int)
        answer = 0

        for num in nums:
            current_gcd = gcd(num, k)

            for previous_gcd, frequency in gcd_count.items():
                if (current_gcd * previous_gcd) % k == 0:
                    answer += frequency

            gcd_count[current_gcd] += 1

        return answer

The implementation follows the algorithm directly.

The gcd_count hash map stores frequencies of previously encountered gcd values. This allows efficient counting because multiple earlier numbers may share the same gcd.

For each number:

We compute its gcd with k
We test compatibility with all previous gcd groups
We add matching frequencies to the answer
We store the current gcd for future processing

The expression:

(current_gcd * previous_gcd) % k == 0

is the key mathematical condition that determines whether two numbers form a valid pair.

Using defaultdict(int) simplifies frequency management because missing keys automatically start at zero.

Go Solution

package main

import "math"

func gcd(a int, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func countPairs(nums []int, k int) int64 {
	gcdCount := make(map[int]int64)
	var answer int64 = 0

	for _, num := range nums {
		currentGCD := gcd(num, k)

		for previousGCD, frequency := range gcdCount {
			if (currentGCD*previousGCD)%k == 0 {
				answer += frequency
			}
		}

		gcdCount[currentGCD]++
	}

	return answer
}

func main() {
	_ = math.MaxInt
}

The Go solution mirrors the Python implementation closely.

One important difference is the use of int64 for the answer and frequency counts. The number of valid pairs can exceed the range of a 32-bit integer because the maximum number of pairs is:

$$\frac{10^5 \times 99999}{2}$$

which is approximately 5 * 10^9.

The gcd helper function uses the standard Euclidean algorithm.

Go maps require explicit existence handling, but since incrementing a missing integer key defaults to zero, the implementation remains concise.

Worked Examples

Example 1

Input:

nums = [1,2,3,4,5]
k = 2

We process elements one by one.

Current Number	gcd(num, 2)	Existing gcd map	Valid Matches	Answer After
1	1	{}	0	0
2	2	{1:1}	1	1
3	1	{1:1, 2:1}	1	2
4	2	{1:2, 2:1}	3	5
5	1	{1:2, 2:2}	2	7

Final answer:

Explanation of one step:

When processing 4:

gcd(4, 2) = 2
Compare with previous gcds:
2 * 1 = 2, divisible by 2
2 * 2 = 4, divisible by 2

All previous elements form valid pairs with 4.

Example 2

Input:

nums = [1,2,3,4]
k = 5

Current Number	gcd(num, 5)	Existing gcd map
1	1	{}
2	1	{1:1}
3	1	{1:2}
4	1	{1:3}

Since:

$$1 \times 1 \not\equiv 0 \pmod{5}$$

no valid pair exists.

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × d)	For each number, iterate through stored gcd groups
Space	O(d)	Hash map stores gcd frequencies

Here, d is the number of distinct divisors of k.

Since k ≤ 10^5, the number of divisors is relatively small in practice. This makes the solution efficient enough for the given constraints.

The algorithm avoids checking all pairs directly and instead groups numbers by their gcd contribution relative to k.

Test Cases

from typing import List

s = Solution()

assert s.countPairs([1,2,3,4,5], 2) == 7  # provided example
assert s.countPairs([1,2,3,4], 5) == 0  # no valid pairs

assert s.countPairs([2,2,2], 2) == 3  # every pair valid
assert s.countPairs([1,1,1], 2) == 0  # no pair divisible

assert s.countPairs([5,10,15], 5) == 3  # all products divisible by 5
assert s.countPairs([6,2,3], 6) == 2  # mixed divisibility

assert s.countPairs([100000,100000], 100000) == 1  # large values
assert s.countPairs([1], 1) == 0  # single element

assert s.countPairs([4,8,16,32], 8) == 6  # all pairs valid
assert s.countPairs([7,11,13], 6) == 0  # pairwise incompatible

assert s.countPairs([2,3,4,9], 6) == 4  # multiple gcd combinations
assert s.countPairs([12,18,24,36], 12) == 6  # strong factor overlap

Test Summary

Test	Why
`[1,2,3,4,5], k=2`	Validates provided example
`[1,2,3,4], k=5`	Validates no-solution case
`[2,2,2], k=2`	Every pair valid
`[1,1,1], k=2`	No products divisible
`[5,10,15], k=5`	Shared factors across all numbers
`[6,2,3], k=6`	Partial factor contributions
`[100000,100000], k=100000`	Large boundary values
`[1], k=1`	Minimum array size
`[4,8,16,32], k=8`	Dense valid pairing
`[7,11,13], k=6`	Prime incompatibility
`[2,3,4,9], k=6`	Different gcd categories
`[12,18,24,36], k=12`	Multiple overlapping divisors

Edge Cases

Case 1: `k = 1`

When k = 1, every integer is divisible by 1. Therefore, every possible pair is valid.

A buggy implementation might overcomplicate the divisibility logic or accidentally skip pairs. In this solution, every gcd becomes 1, and:

$$(1 \times 1) \bmod 1 = 0$$

so all pairs are counted correctly.

Case 2: Single Element Array

If the array contains only one element, no valid pair can exist because pairs require two distinct indices.

The implementation naturally handles this because the loop never finds any previously stored gcd values before inserting the first element.

Case 3: Numbers Individually Not Divisible by `k`

Some valid pairs arise only when two numbers combine their factors.

For example:

nums = [2, 3]
k = 6

Neither 2 nor 3 is divisible by 6, but:

$$2 \times 3 = 6$$

which is divisible by 6.

A naive optimization that only checks numbers individually divisible by k would fail here. The gcd-based approach correctly recognizes that:

$$\gcd(2,6)=2$$

and

$$\gcd(3,6)=3$$

and:

$$2 \times 3 \equiv 0 \pmod{6}$$

so the pair is counted.

Case 4: Many Duplicate Values

Arrays with many repeated numbers can create very large numbers of valid pairs.