Sorted GCD Pair Queries solution and explanation
Google
9 more videos on this problem
Sorted GCD Pair Queries | Deep Dive | Intuition | Dry Run | Leetcode 3312 | codestorywithMIKcodestorywithMIK · 51:40 · 8K views
3312. Sorted GCD Pair Queries | Leetcode Daily - PythonLeetcode Daily · 8:45 · 2K views
LeetCode 3312 Hard Explained | Sorted GCD Pair Queries | Java | Best Optimized SolutionExplainedbychhavi · 10:12 · 1K views
leetcode 3312 | Sorted GCD Pair Queries | Sieve method + inclusion - exclusion + Prefix sum | POTDCode With Vick · 25:51 · 1K views
Leetcode | Weekly Contest 418 | 3312. Sorted GCD Pair Queries | 3310. Remove Methods From ProjectPretest Passed · 34:36 · 1K views
Sorted GCD Pair Queries | Leetcode 3312 | Java | HindiKernel Queen 👑 · 18:50 · 1K views
Sorted GCD Pair Queries | LeetCode 3312 - Pythonimpoldev · 19:18 · 952 views
3312. Sorted GCD Pair Queries | Weekly Contest 418 Solutionog_prakash · 22:35 · 752 views
3312. Sorted GCD Pair Queries (Leetcode Hard)Programming Live with Larry · 1:11:16 · 742 views
Sorted GCD Pair Queries | Leetcode - 3312Shivam Gupta · 31:15 · 664 views
The problem
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) / 2
Approach overview
Problem Overview: You receive an integer array and multiple queries related to the sorted list of GCD values generated from every pair (i, j) where i < j. The core task is to compute pairwise gcd(nums[i], nums[j]), conceptually sort those values, and answer queries about positions in that sorted sequence.
Approach 1: Brute Force GCD Calculation for All Pairs (Time: O(n2 log V + n2 log n), Space: O(n2))
Generate every possible pair using two nested loops. For each pair, compute the GCD using the Euclidean algorithm and append the result to a list. After collecting all n(n-1)/2 GCD values, sort the list so that queries referring to positions in the sorted order can be answered directly. Each query becomes a simple index lookup in the sorted array.
The algorithm is straightforward and guarantees correctness. The cost comes from generating all pairs and sorting a potentially large list of GCD values. For large inputs this becomes impractical because both time and memory grow quadratically. Still, it clearly demonstrates the mechanics of pair enumeration and GCD computation using classic number theory techniques.
Approach 2: Optimized with Early Termination of GCD Calculation (Time: O(n2 log V) average, Space: O(n2))
This approach keeps the same pair enumeration but reduces the cost of computing each GCD. While applying the Euclidean algorithm, you terminate early if the intermediate result becomes 1. Once the GCD hits 1, further modulo steps cannot reduce it further, so the calculation stops immediately. In many real datasets where numbers share few factors, most pair GCDs quickly converge to 1, cutting the average computation time.
The rest of the pipeline remains the same: append each computed GCD to a list, sort the resulting values, and answer queries directly from the sorted array. This technique improves runtime in practice without changing asymptotic pair generation cost. It is still fundamentally a quadratic approach but performs noticeably better on random inputs.
The implementation uses simple iteration over the array, repeated Euclidean GCD calls, and a final sorting step. Query answering can also use prefix indexing or direct access patterns similar to those used in prefix sum style query handling.
Recommended for interviews: Start with the brute force method to show you understand how pairwise GCD generation works. Then discuss optimization opportunities such as early termination in the Euclidean algorithm or reducing redundant work. Interviewers expect you to recognize the quadratic bottleneck and reason about improving pairwise computations, even if the baseline solution already demonstrates solid understanding.
Approach 1: Brute Force GCD Calculation for All Pairs
This approach involves calculating the GCD of all possible pairs (i, j) where i < j and storing these values in an array. Once we have all the GCD values, we sort this array and use it to answer the queries by simple index lookup.
from math import gcd
def find_gcd_pairs(nums, queries):
n = len(nums)
gcd_pairs = []
for i in range(n):
for j in range(i+1, n):
gcd_pairs.append(gcd(nums[i], nums[j]))
gcd_pairs.sort()
return [gcd_pairs[q] for q in queries]#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
vector<int> findGcdPairs(const vector<int>& nums, const vector<int>& queries) {
vector<int> gcd_pairs;
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
gcd_pairs.push_back(gcd(nums[i], nums[j]));
}
}
sort(gcd_pairs.begin(), gcd_pairs.end());
vector<int> result;
for (int q : queries) {
result.push_back(gcd_pairs[q]);
}
return result;
}The function iterates over all pairs of indices to calculate their GCD, storing each result in gcd_pairs. After calculating the GCD for all pairs, it sorts this list. Finally, it constructs the answer list by accessing gcd_pairs at each index specified by queries.
Time Complexity: O(n2 log n) due to the double loop for GCD calculation and sorting.
Space Complexity: O(n2) for storing the GCD pairs.
Approach 2: Optimized with Early Termination of GCD Calculation
This approach leverages the properties of the GCD function to potentially reduce the number of comparisons needed to calculate the GCD for a pair. For example, if during the GCD calculation you find a divisor of 1, you can stop early since the minimum possible GCD is 1.
import java.util.*;
public class Solution {
public static List<Integer> findGcdPairs(int[] nums, int[] queries) {
List<Integer> gcdPairs = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
for (int j = i+1; j < nums.length; j++) {
gcdPairs.add(gcd(nums[i], nums[j]));
}
}
Collections.sort(gcdPairs);
List<Integer> result = new ArrayList<>();
for (int q : queries) {
result.add(gcdPairs.get(q));
}
return result;
}
private static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
}using System;
using System.Collections.Generic;
public class Solution {
public static List<int> FindGcdPairs(int[] nums, int[] queries) {
var gcdPairs = new List<int>();
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
gcdPairs.Add(Gcd(nums[i], nums[j]));
}
}
gcdPairs.Sort();
var result = new List<int>();
foreach (var q in queries) {
result.Add(gcdPairs[q]);
}
return result;
}
private static int Gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
}This Java solution employs a custom GCD function similar to the Euclidean algorithm to ensure consistent performance, especially when dealing with cases that might result in quick termination if the GCD turns out to be 1.
Time Complexity: O(n2 log n)
Space Complexity: O(n2)
Approach 3: Preprocessing + Prefix Sum + Binary Search
We can preprocess to obtain the occurrence count of the greatest common divisor (GCD) of all pairs in the array nums, recorded in the array cntG. Then, we calculate the prefix sum of the array cntG. Finally, for each query, we can use binary search to find the index of the first element in the array cntG that is greater than queries[i], which is the answer.
Let mx denote the maximum value in the array nums, and let cnt record the occurrence count of each number in the array nums. Let cntG[i] denote the number of pairs in the array nums whose GCD is equal to i. To calculate cntG[i], we can follow these steps:
- Calculate the occurrence count
vof multiples ofiin the arraynums. Then, the number of pairs formed by any two elements from these multiples must have a GCD that is a multiple ofi, i.e.,cntG[i]needs to be increased byv times (v - 1) / 2; - We need to exclude pairs whose GCD is a multiple of
iand greater thani. Therefore, for multiplesjofi, we need to subtractcntG[j].
The above steps require us to traverse i from large to small so that when calculating cntG[i], we have already calculated all cntG[j].
Finally, we calculate the prefix sum of the array cntG, and for each query, we can use binary search to find the index of the first element in the array cntG that is greater than queries[i], which is the answer.
The time complexity is O(n + (M + q) times log M), and the space complexity is O(M). Here, n and M represent the length and the maximum value of the array nums, respectively, and q represents the number of queries.
func gcdValues(nums []int, queries []int64) (ans []int) {
mx := slices.Max(nums)
cnt := make([]int, mx+1)
cntG := make([]int, mx+1)
for _, x := range nums {
cnt[x]++
}
for i := mx; i > 0; i-- {
var v int
for j := i; j <= mx; j += i {
v += cnt[j]
cntG[i] -= cntG[j]
}
cntG[i] += v * (v - 1) / 2
}
for i := 2; i <= mx; i++ {
cntG[i] += cntG[i-1]
}
for _, q := range queries {
ans = append(ans, sort.SearchInts(cntG, int(q)+1))
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force GCD Calculation for All Pairs | Time Complexity: O(n2 log n) due to the double loop for GCD calculation and sorting. |
| Optimized with Early Termination of GCD Calculation | Time Complexity: O(n2 log n) |
| Preprocessing + Prefix Sum + Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force GCD for All Pairs | O(n² log V + n² log n) | O(n²) | Small arrays or when demonstrating the baseline logic in interviews |
| Early-Termination Euclidean GCD | O(n² log V) average | O(n²) | General case when many pairs quickly produce GCD = 1 |
Frequently asked questions
Is Sorted GCD Pair Queries easy or hard?
Sorted GCD Pair Queries is categorized as a Hard problem because the naive approach is simple but inefficient. Efficient reasoning often requires number theory concepts, pair counting strategies, and optimized query processing.
Sorted GCD Pair Queries Python/Java solution
Python implementations typically use the built-in math.gcd function inside nested loops to compute pairwise GCD values. Java and C++ versions implement the Euclidean algorithm directly. After collecting results, the list is sorted and queries return the value at the requested sorted position.
How to solve Sorted GCD Pair Queries in O(n)?
An O(n) solution is not achievable for the naive pair-generation version because the number of pairs itself is O(n^2). Advanced optimizations rely on number theory and counting frequencies of divisors rather than explicitly enumerating pairs. Those techniques reduce the effective computation but still depend on the numeric range of values.
What is the best approach for Sorted GCD Pair Queries?
The most practical baseline approach enumerates every pair of elements, computes the GCD using the Euclidean algorithm, stores the results, sorts them, and answers queries by index. An optimization is to terminate the GCD calculation early once the value becomes 1, which improves average performance when numbers share few factors.
Is Sorted GCD Pair Queries asked at Google/Amazon/Meta?
Problems involving pairwise GCD computations, divisor counting, and query processing appear in interviews at large tech companies including Google and Amazon. Variants typically test number theory knowledge, efficient pair counting, and query handling techniques such as prefix sums or binary search.
What data structure is used in Sorted GCD Pair Queries?
Common implementations rely on arrays or dynamic lists to store GCD values for each pair. Some optimized strategies also use hash tables for frequency counting and prefix-sum arrays to answer queries efficiently after preprocessing.
What is the time complexity of Sorted GCD Pair Queries?
A straightforward solution requires generating all pairs, which is O(n^2). Each GCD calculation takes O(log V) time where V is the maximum value in the array, and sorting the resulting list adds O(n^2 log n). The total complexity is roughly O(n^2 log V + n^2 log n) with O(n^2) space.