Count Array Pairs Divisible by K

Problem

Given a 0-indexed integer array nums of length n and an integer k, return thenumber of pairs (i, j) such that:

• 0 <= i < j <= n - 1 and
• nums[i] * nums[j] is divisible by k.

Examples

Example 1

    
    
    Input: nums = [1,2,3,4,5], k = 2
    Output: 7
    Explanation: 
    The 7 pairs of indices whose corresponding products are divisible by 2 are
    (0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), and (3, 4).
    Their products are 2, 4, 6, 8, 10, 12, and 20 respectively.
    Other pairs such as (0, 2) and (2, 4) have products 3 and 15 respectively, which are not divisible by 2.    
    

Example 2

    
    
    Input: nums = [1,2,3,4], k = 5
    Output: 0
    Explanation: There does not exist any pair of indices whose corresponding product is divisible by 5.
    

Constraints

• 1 <= nums.length <= 10^5
• 1 <= nums[i], k <= 10^5

Solution

Method 1 – GCD Counting and Number Theory 1

Intuition

For a pair (i, j), nums[i] * nums[j] is divisible by k if and only if gcd(nums[i], k) * gcd(nums[j], k) is divisible by k. We can count the frequency of each possible gcd value with k, and for each nums[i], count how many previous numbers have a gcd such that their product with nums[i]'s gcd is divisible by k.

Approach

1. For each number in nums, compute gcd(num, k).
2. Use a hash map to count the frequency of each gcd value seen so far.
3. For each nums[i], for each gcd value in the map, if (gcd(nums[i], k) * g) % k == 0, add its frequency to the answer.
4. Add the current gcd to the map.
5. Return the total count.

Code

C++

class Solution {
public:
    long long countPairs(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        long long ans = 0;
        for (int x : nums) {
            int g = gcd(x, k);
            for (auto& [d, cnt] : freq) {
                if (1LL * g * d % k == 0) ans += cnt;
            }
            freq[g]++;
        }
        return ans;
    }
    int gcd(int a, int b) {
        return b ? gcd(b, a % b) : a;
    }
};

Go

func countPairs(nums []int, k int) int64 {
    freq := map[int]int{}
    var ans int64
    gcd := func(a, b int) int {
        for b != 0 {
            a, b = b, a%b
        }
        return a
    }
    for _, x := range nums {
        g := gcd(x, k)
        for d, cnt := range freq {
            if g*d%k == 0 {
                ans += int64(cnt)
            }
        }
        freq[g]++
    }
    return ans
}

Java

class Solution {
    public long countPairs(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        long ans = 0;
        for (int x : nums) {
            int g = gcd(x, k);
            for (int d : freq.keySet()) {
                if ((long)g * d % k == 0) ans += freq.get(d);
            }
            freq.put(g, freq.getOrDefault(g, 0) + 1);
        }
        return ans;
    }
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

Kotlin

class Solution {
    fun countPairs(nums: IntArray, k: Int): Long {
        val freq = mutableMapOf<Int, Int>()
        var ans = 0L
        fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
        for (x in nums) {
            val g = gcd(x, k)
            for ((d, cnt) in freq) {
                if (1L * g * d % k == 0L) ans += cnt
            }
            freq[g] = freq.getOrDefault(g, 0) + 1
        }
        return ans
    }
}

Python

class Solution:
    def countPairs(self, nums: list[int], k: int) -> int:
        from math import gcd
        from collections import Counter
        freq = Counter()
        ans = 0
        for x in nums:
            g = gcd(x, k)
            for d, cnt in freq.items():
                if g * d % k == 0:
                    ans += cnt
            freq[g] += 1
        return ans

Rust

impl Solution {
    pub fn count_pairs(nums: Vec<i32>, k: i32) -> i64 {
        use std::collections::HashMap;
        fn gcd(mut a: i32, mut b: i32) -> i32 {
            while b != 0 {
                let t = b;
                b = a % b;
                a = t;
            }
            a
        }
        let mut freq = HashMap::new();
        let mut ans = 0i64;
        for &x in &nums {
            let g = gcd(x, k);
            for (&d, &cnt) in &freq {
                if (g as i64 * d as i64) % k as i64 == 0 {
                    ans += cnt as i64;
                }
            }
            *freq.entry(g).or_insert(0) += 1;
        }
        ans
    }
}

TypeScript

class Solution {
    countPairs(nums: number[], k: number): number {
        const freq = new Map<number, number>();
        let ans = 0;
        const gcd = (a: number, b: number): number => b === 0 ? a : gcd(b, a % b);
        for (const x of nums) {
            const g = gcd(x, k);
            for (const [d, cnt] of freq.entries()) {
                if (g * d % k === 0) ans += cnt;
            }
            freq.set(g, (freq.get(g) ?? 0) + 1);
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n * t), where n is the length of nums and t is the number of unique gcd values (at most O(sqrt(k))).
• 🧺 Space complexity: O(t), for the frequency map.