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
andnums[i] * nums[j]
is divisible byk
.
Examples
Example 1
|
|
Example 2
|
|
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
- For each number in nums, compute gcd(num, k).
- Use a hash map to count the frequency of each gcd value seen so far.
- 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.
- Add the current gcd to the map.
- Return the total count.
Code
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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.