Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs (i, j) such that:
0 <= i < j <= n - 1 andnums[i] * nums[j] is divisible by k.
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 <= 1051 <= nums[i], k <= 105Problem 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.
This approach involves checking every possible pair (i, j) to see if the product of the elements at these indices is divisible by k. It iterates over each pair and uses the modulus operator for the divisibility check.
The function iterates through each possible pair in the array. For each pair, it checks if the product of the numbers at these indices is divisible by k. If so, it increments the count.
Time Complexity: O(n^2) - due to the nested loops checking each pair.
Space Complexity: O(1) - only uses a constant amount of extra space.
This approach reduces the number of checks needed by considering the divisibility of products using modular arithmetic. It involves counting occurrences of remainders of elements divided by factors of k. We precompute the frequency of these modules and use them to count divisible pairs effectively.
The C code uses an array to keep track of the frequency of each remainder when elements are divided by k. For each element, it calculates its remainder and looks for the complement remainder pair needed to form a product divisible by k.
Time Complexity: O(n) - each element is iterated once.
Space Complexity: O(k) - requires space for storing k frequencies.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) - due to the nested loops checking each pair. |
| Optimized Approach Using Remainders | Time Complexity: O(n) - each element is iterated once. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n²) | O(1) | Small arrays or quick correctness verification |
| GCD Hashing (Number Theory Optimization) | O(n log k) | O(d) where d is number of divisors of k | General case and interview settings with large n |
Hard Coding Test Problem | Leetcode Weekly Episode 5 | Leetcode 2183 | Number Theory • Vivek Gupta • 6,018 views views
Watch 9 more video solutions →Practice Count Array Pairs Divisible by K with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor