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 <= 105The key observation in #2183 Count Array Pairs Divisible by K is that a pair (i, j) is valid if (nums[i] * nums[j]) % k == 0. Instead of checking every pair, we use number theory to simplify the condition. For each number x, compute g = gcd(x, k). This represents how much of k's factors are already present in x.
Maintain a frequency map of previously seen gcd values. For the current element, check which earlier gcd values g2 satisfy (g * g2) % k == 0. Each valid match contributes to the answer. This reduces the brute-force O(n^2) pair checking into a much smaller set of gcd combinations.
By leveraging the limited number of divisors of k and hashing frequencies, the algorithm runs efficiently in about O(n * d), where d is the number of distinct gcd values related to k. Space complexity is O(d) for storing gcd counts.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| GCD + Hash Map Counting | O(n * d) where d is the number of divisors of k | O(d) |
Techdose
Use these hints if you're stuck. Try solving on your own first.
For any element in the array, what is the smallest number it should be multiplied with such that the product is divisible by k?
The smallest number which should be multiplied with nums[i] so that the product is divisible by k is k / gcd(k, nums[i]). Now think about how you can store and update the count of such numbers present in the array efficiently.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Using gcd(num, k) captures how much of k's factors are already contained in the number. By comparing gcd values instead of full numbers, we can efficiently determine whether the product of two elements will be divisible by k.
Yes, problems involving divisibility, gcd, and pair counting appear in many technical interviews. This problem tests knowledge of number theory, hashing, and optimization techniques commonly expected in top tech company interviews.
A hash map (or dictionary) is typically used to store the frequency of gcd values encountered so far. This allows fast lookups when checking which previous values can form valid divisible pairs.
The optimal approach uses number theory with GCD and a hash map. For each number, compute gcd(num, k) and count previously seen gcd values that combine to make the product divisible by k. This avoids the O(n^2) brute-force pair checking.