Sorted GCD Pair Queries - Video Solutions

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(n² log V + n² log n), Space: O(n²))

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(n² log V) average, Space: O(n²))

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.