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].
Example 3:
Input: nums = [2,2], queries = [0,0]
Output: [2,2]
Explanation:
gcdPairs = [2].
Constraints:
2 <= n == nums.length <= 1051 <= nums[i] <= 5 * 1041 <= queries.length <= 1050 <= queries[i] < n * (n - 1) / 2The key challenge in #3312 Sorted GCD Pair Queries is efficiently determining the position of pairwise gcd(a, b) values when all pairs are sorted. A brute-force approach that computes GCD for every pair would take O(n^2) time, which is infeasible for large inputs.
An optimized strategy uses number theory and counting. First, compute the frequency of each number in the array. Then iterate over possible GCD values and count how many pairs have that exact GCD by aggregating counts of multiples. Using an inclusion–exclusion style adjustment (similar to a sieve), you can derive the exact number of pairs for each GCD value. Once these counts are known, build a prefix sum array to represent how many pairs fall up to each GCD value.
Finally, each query can be answered using binary search on the prefix array to locate the GCD corresponding to the requested rank. This transforms the problem into efficient preprocessing plus fast query handling.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Frequency counting + GCD multiple aggregation + prefix sums | O(M log M + Q log M) | O(M) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Try counting the number of pairs that have a GCD of <code>g</code.
Use inclusion-exclusion.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
A brute-force solution requires evaluating GCD for every pair, which takes O(n^2) time. For large arrays, this quickly becomes too slow, making number-theoretic counting techniques necessary.
Problems involving GCD counting, prefix sums, and number theory patterns are common in advanced coding interviews. While this exact question may vary, similar concepts appear in FAANG-level interview preparation.
Frequency arrays and prefix sum arrays are the most important structures. They allow efficient counting of values and quick lookup of pair rankings when combined with binary search.
The optimal approach uses number theory and counting. Instead of computing GCD for every pair, it counts how many pairs produce each possible GCD using multiples and inclusion–exclusion logic. A prefix sum of these counts allows fast query resolution via binary search.