Count Product-Divisible Pairs
Reported by candidates from Motive's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The mistake that sinks a first attempt on this Motive OA, reported in September 2024, is writing the obvious double loop. With nums up to 100000 long, O(n^2) pairs times a modulo check will blow past the limit. The real question is counting pairs whose product is divisible by k, and it's a gcd and hash-table counting problem. If you blank on the trick during the live assessment, StealthCoder runs invisibly as a safety net and gives you the approach while you type. But the idea is short enough to learn tonight.
The problem
Given an integer array nums and a positive integer k, return the number of index pairs i < j such that nums[i] * nums[j] is divisible by k. Function countProductDivisiblePairs(nums: int[], k: int) → long Examples Example 1 nums = [1,2,3,4,5] k = 2 return = 7 Example 2 nums = [1,2,3,4] k = 5 return = 0 Constraints 1 <= nums.length <= 100000. 0 <= nums[i] <= 10^9. 1 <= k <= 10^5.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick: nums[i] * nums[j] is divisible by k exactly when gcd(nums[i], k) * gcd(nums[j], k) is divisible by k. So replace every number with g = gcd(x, k). Since k is at most 10^5, there are only as many distinct g values as divisors of k, which is small (at most 128). Count how many numbers have each g in a hash map. Then loop over all pairs of distinct divisor values (a, b), and if a * b % k == 0, add cnt[a] * cnt[b] when a < b, or cnt[a] * (cnt[a] - 1) / 2 when a == b. The pitfalls are overflow, so use a 64-bit result, and zeros. gcd(0, k) is k, which works naturally since 0 times anything is divisible by k. Don't skip it. StealthCoder is the hedge if the gcd reduction doesn't come to you under pressure.
The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.
You can drill Count Product-Divisible Pairs cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play.
Get StealthCoderRelated leaked OAs
This OA pattern shows up on LeetCode as count array pairs divisible by k. If you have time before the OA, drill that.
You've seen the question.
Make sure you actually pass Motive's OA.
Motive reuses patterns across OAs. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Count Product-Divisible Pairs FAQ
What's the trick for Count Product-Divisible Pairs?+
Reduce each number to gcd(num, k). A product is divisible by k only if the product of those gcds is divisible by k. That collapses 100000 values into a handful of distinct divisors of k, so you count by group instead of by pair.
Why does brute force fail here?+
With n up to 100000 there are about 5 billion pairs. Even a cheap modulo check per pair is far too slow. The Motive OA is built so the nested loop times out, and you need the gcd grouping to get near O(n log k + d^2).
How do I handle zeros in nums?+
gcd(0, k) equals k, so zeros land in the group with value k. Any product with that group is divisible by k, since k times anything is a multiple of k. No special casing is needed if your gcd function handles 0 correctly.
Do I need a 64-bit return type?+
Yes. The function returns long for a reason. With 100000 elements you can have nearly 5 billion valid pairs, which overflows a 32-bit int. Use long for the counts and for the multiplication cnt[a] * cnt[b].
How do I prepare for this in 48 hours?+
Write the gcd-bucket solution from scratch twice. Test it on both examples, then on an all-zeros array and on k = 1. Know the equal-group case, where you use c * (c - 1) / 2. That covers nearly every bug people hit on this problem.