Skip to main content
Talentd

Sorted GCD Pair Queries - Solution & Explanation

HardArrayHash TableMathBinary Search14 min readAsked at: Google
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 5 * 104
  • 1 <= queries.length <= 105
  • 0 <= 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.

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

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.

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.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(n2 log n)
Space Complexity: O(n2)

Try this approach in the editor →

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:

  1. Calculate the occurrence count v of multiples of i in the array nums. Then, the number of pairs formed by any two elements from these multiples must have a GCD that is a multiple of i, i.e., cntG[i] needs to be increased by v times (v - 1) / 2;
  2. We need to exclude pairs whose GCD is a multiple of i and greater than i. Therefore, for multiples j of i, we need to subtract cntG[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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force GCD Calculation for All Pairs

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.

Optimized with Early Termination of GCD Calculation

Time Complexity: O(n2 log n)
Space Complexity: O(n2)

Preprocessing + Prefix Sum + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force GCD for All PairsO(n² log V + n² log n)O(n²)Small arrays or when demonstrating the baseline logic in interviews
Early-Termination Euclidean GCDO(n² log V) averageO(n²)General case when many pairs quickly produce GCD = 1

Video Solution

Sorted GCD Pair Queries | Deep Dive | Intuition | Dry Run | Leetcode 3312 | codestorywithMIK • codestorywithMIK • 8,127 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Sorted GCD Pair Queries with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays