Count Array Pairs Divisible by K
Problem
Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs of indices (i, j) with 0 ≤ i < j ≤ n − 1 such that the product nums[i] * nums[j] is divisible by k.
nums = [1,2,3,4,5], k = 27nums = [1,2,3,4], k = 50def count_pairs(nums, k):
from math import gcd
count = {}
ans = 0
for x in nums:
g = gcd(x, k)
for g2, c in count.items():
if (g * g2) % k == 0:
ans += c
count[g] = count.get(g, 0) + 1
return ansfunction countPairs(nums, k) {
const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
const count = new Map();
let ans = 0;
for (const x of nums) {
const g = gcd(x, k);
for (const [g2, c] of count) {
if ((g * g2) % k === 0) ans += c;
}
count.set(g, (count.get(g) || 0) + 1);
}
return ans;
}long countPairs(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
long ans = 0;
for (int x : nums) {
int g = gcd(x, k);
for (var e : count.entrySet()) {
if ((long) g * e.getKey() % k == 0) ans += e.getValue();
}
count.merge(g, 1, Integer::sum);
}
return ans;
}
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }long long countPairs(vector<int>& nums, int k) {
unordered_map<int, int> count;
long long ans = 0;
for (int x : nums) {
int g = __gcd(x, k);
for (auto& [g2, c] : count) {
if ((long long) g * g2 % k == 0) ans += c;
}
count[g]++;
}
return ans;
}Explanation
The brute force compares every pair, which is O(n²) — far too slow for n up to 10⁵. The key insight is that whether nums[i] * nums[j] is divisible by k depends only on each value's greatest common divisor with k, not the value itself.
Let g = gcd(x, k). The part of x that helps reach a multiple of k is exactly g; the rest is coprime to k and contributes nothing. So a product x · y is divisible by k precisely when gcd(x,k) · gcd(y,k) is divisible by k.
We sweep left to right, keeping a hash map count from a gcd value to how many earlier elements produced it. For each new x we compute its gcd g, then look at every distinct gcd key g2 already stored: if g · g2 is a multiple of k, every one of those count[g2] earlier elements pairs with the current one, so we add that count to the answer.
After counting, we record g in the map for future elements. Because every gcd is a divisor of k, the map holds at most d(k) distinct keys — the number of divisors of k — which is tiny. The inner loop runs over those keys, not over all elements.
For nums = [1,2,3,4,5], k = 2 the gcds are 1, 2, 1, 2, 1. Pairs of gcds whose product is even are (1,2), (2,1), (2,2). Walking through the array and accumulating matches yields 7.