In this guide, you will get 3312. Sorted GCD Pair Queries LeetCode Solution with the best time and space complexity. The solution to Sorted GCD Pair Queries problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
You are given an integer array nums of length n and an integer array queries.
Let gcdPairs denote an array obtained by calculating the GCD of all possible pairs (nums[i], nums[j]), where 0 <= i < j < n, and then sorting these values in ascending order.
For each query queries[i], you need to find the element at index queries[i] in gcdPairs.
Return an integer array answer, where answer[i] is the value at gcdPairs[queries[i]] for each query.
The term gcd(a, b) denotes the greatest common divisor of a and b.
Example 1:
Input: nums = [2,3,4], queries = [0,2,2]
Output: [1,2,2]
Explanation:
gcdPairs = [gcd(nums[0], nums[1]), gcd(nums[0], nums[2]), gcd(nums[1], nums[2])] = [1, 2, 1].
After sorting in ascending order, gcdPairs = [1, 1, 2].
So, the answer is [gcdPairs[queries[0]], gcdPairs[queries[1]], gcdPairs[queries[2]]] = [1, 2, 2].
Example 2:
Input: nums = [4,4,2,1], queries = [5,3,1,0]
Output: [4,2,1,1]
Explanation:
gcdPairs sorted in ascending order is [1, 1, 1, 2, 2, 4].
Time Complexity: O(n \cdot \sqrt{\max(\texttt{nums})})
Space Complexity: O(\max(\texttt{nums}))
3312. Sorted GCD Pair Queries LeetCode Solution in C++
class Solution {
public:
vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {
const int maxNum = ranges::max(nums);
vector<int> ans;
// countDivisor[d] := the number of `nums` having `num % d == 0`
vector<int> countDivisor(maxNum + 1);
// countGcdPair[g] := the number of pairs having gcd == g
vector<long> countGcdPair(maxNum + 1);
// prefixCountGcdPair[g] := the number of pairs having gcd <= g
vector<long> prefixCountGcdPair{0};
for (const int num : nums)
for (int i = 1; i * i <= num; ++i)
if (num % i == 0) {
++countDivisor[i];
if (i != num / i)
++countDivisor[num / i];
}
for (int gcd = maxNum; gcd >= 1; --gcd) {
// There are C(countDivisor[gcd], 2) pairs that have a common divisor
// that's a multiple of `gcd` (including the one that equals to `gcd`).
// So, substract the multiples of `gcd` to have the number of pairs with a
// gcd that's exactly `gcd`.
countGcdPair[gcd] =
countDivisor[gcd] * static_cast<long>(countDivisor[gcd] - 1) / 2;
for (int largerGcd = 2 * gcd; largerGcd <= maxNum; largerGcd += gcd)
countGcdPair[gcd] -= countGcdPair[largerGcd];
}
for (int gcd = 1; gcd <= maxNum; ++gcd)
prefixCountGcdPair.push_back(prefixCountGcdPair.back() +
countGcdPair[gcd]);
for (const long query : queries)
ans.push_back(getNthGcdPair(query, prefixCountGcdPair));
return ans;
}
private:
// Returns the `query`-th gcd pair.
int getNthGcdPair(long query, const vector<long>& prefixCountGcdPair) {
int l = 1;
int r = prefixCountGcdPair.size() - 1;
while (l < r) {
const int m = (l + r) / 2;
if (prefixCountGcdPair[m] < query + 1)
l = m + 1;
else
r = m;
}
return l;
}
}; /* code provided by PROGIEZ */
3312. Sorted GCD Pair Queries LeetCode Solution in Java
class Solution {
public int[] gcdValues(int[] nums, long[] queries) {
int maxNum = Arrays.stream(nums).max().getAsInt();
int[] ans = new int[queries.length];
// countDivisor[d] := the number of `nums` having `num % d == 0`
int[] countDivisor = new int[maxNum + 1];
// countGcdPair[g] := the number of pairs having gcd == g
long[] countGcdPair = new long[maxNum + 1];
// prefixCountGcdPair[g] := the number of pairs having gcd <= g
long[] prefixCountGcdPair = new long[maxNum + 1];
for (final int num : nums)
for (int i = 1; i * i <= num; ++i)
if (num % i == 0) {
++countDivisor[i];
if (i != num / i)
++countDivisor[num / i];
}
for (int gcd = maxNum; gcd >= 1; --gcd) {
// There are C(countDivisor[gcd], 2) pairs that have a common divisor
// that's a multiple of `gcd` (including the one that equals to `gcd`).
// So, substract the multiples of `gcd` to have the number of pairs with a
// gcd that's exactly `gcd`.
countGcdPair[gcd] = (long) countDivisor[gcd] * (countDivisor[gcd] - 1) / 2;
for (int largerGcd = 2 * gcd; largerGcd <= maxNum; largerGcd += gcd)
countGcdPair[gcd] -= countGcdPair[largerGcd];
}
for (int gcd = 1; gcd <= maxNum; ++gcd)
prefixCountGcdPair[gcd] = prefixCountGcdPair[gcd - 1] + countGcdPair[gcd];
for (int i = 0; i < queries.length; ++i)
ans[i] = getNthGcdPair(queries[i], prefixCountGcdPair);
return ans;
}
// Returns the `query`-th gcd pair.
private int getNthGcdPair(long query, long[] prefixCountGcdPair) {
int l = 1;
int r = prefixCountGcdPair.length - 1;
while (l < r) {
int m = (l + r) / 2;
if (prefixCountGcdPair[m] < query + 1)
l = m + 1;
else
r = m;
}
return l;
}
} // code provided by PROGIEZ
3312. Sorted GCD Pair Queries LeetCode Solution in Python
class Solution:
def gcdValues(self, nums: list[int], queries: list[int]) -> list[int]:
maxNum = max(nums)
# countDivisor[d] := the number of `nums` having `num % d == 0`
countDivisor = [0] * (maxNum + 1)
# countGcdPair[g] := the number of pairs having gcd == g
countGcdPair = [0] * (maxNum + 1)
for num in nums:
for i in range(1, math.isqrt(num) + 1):
if num % i == 0:
countDivisor[i] += 1
if i != num // i:
countDivisor[num // i] += 1
for gcd in range(maxNum, 0, -1):
# There are C(countDivisor[gcd], 2) pairs that have a common divisor
# that's a multiple of `gcd` (including the one that equals to `gcd`).
# So, substract the multiples of `gcd` to have the number of pairs with a
# gcd that's exactly `gcd`.
countGcdPair[gcd] = countDivisor[gcd] * (countDivisor[gcd] - 1) // 2
for largerGcd in range(2 * gcd, maxNum + 1, gcd):
countGcdPair[gcd] -= countGcdPair[largerGcd]
# prefixCountGcdPair[g] := the number of pairs having gcd <= g
prefixCountGcdPair = list(itertools.accumulate(countGcdPair))
return [bisect.bisect_left(prefixCountGcdPair, query + 1)
for query in queries] # code by PROGIEZ
