Count Array Pairs Divisible by K - Video Solutions

Problem Overview: Given an integer array nums and an integer k, count pairs (i, j) with i < j such that nums[i] * nums[j] is divisible by k. The challenge is avoiding the obvious quadratic pair check while still verifying the divisibility condition efficiently.

Approach 1: Brute Force Pair Check (O(n²) time, O(1) space)

The direct solution checks every pair in the array. Use two nested loops and compute (nums[i] * nums[j]) % k for each pair. If the remainder is zero, increment the count. This approach uses only constant extra memory and is easy to implement. However, it performs n(n-1)/2 multiplications and modulus operations, which becomes too slow when n grows large. Still useful as a baseline implementation and for verifying correctness during testing.

Approach 2: GCD Hashing with Number Theory (O(n log k) time, O(d) space)

The key observation: instead of checking the product directly, track how much each number contributes toward making a multiple of k. For each value x, compute g = gcd(x, k). This tells you the largest factor of k that x already covers. Two numbers form a valid pair when (g1 * g2) % k == 0. Maintain a hash map counting previously seen gcd values. For the current element, iterate over stored gcd values and add their frequencies when the product condition satisfies divisibility by k. After processing, store the current gcd in the map.

This transformation dramatically reduces the search space. Instead of comparing every pair of indices, you compare factor contributions relative to k. The number of distinct gcd values is bounded by the number of divisors of k, typically small. Each iteration performs a few gcd computations and hash lookups, making the solution scalable even for large arrays.

The optimized approach relies heavily on concepts from math and number theory, while the input itself is handled as a simple array. Understanding how gcd interacts with divisibility is the core trick that converts a quadratic search into a near‑linear solution.

Recommended for interviews: Interviewers expect the GCD + hash map optimization. The brute force approach demonstrates understanding of the requirement, but the optimized method shows you can apply number theory insights to reduce pair comparisons and achieve near-linear complexity.