Sorted GCD Pair Queries — LeetCode Daily Python Solution (5 Billion Pairs, No List) — Fun with Learning Technology

Fun with Learning Technology

Sorted GCD Pair Queries — LeetCode Daily Python Solution (5 Billion Pairs, No List) — Fun with Learning Technology

Introduction

Some LeetCode problems test whether you know a data structure. Others test whether you can recognize that the "obvious" solution is a trap. Sorted GCD Pair Queries belongs firmly in the second category, and it's exactly the kind of problem that separates candidates who can write correct code from candidates who can write code that scales.

Here's the setup that makes this problem interesting: with an array of just 100,000 numbers, the number of pairs you could form crosses five billion. If your first instinct is to compute the GCD of every pair, sort them, and answer queries by index, you'll write code that is completely correct and completely unusable — it will run out of time and memory before it finishes.

This is precisely the pattern interviewers love to probe, because it shows up everywhere in real systems. Precompute a distribution once, then answer a flood of queries instantly. Percentile calculations in analytics dashboards, histogram-backed search in databases, and ranking systems at companies like Google and Meta all lean on this same idea: separate the expensive prep work from the cheap lookup. Learn this pattern once here, and you'll recognize it in a dozen other problems.

Problem Overview

You're given an array of positive integers, nums. Consider every possible pair of indices (i, j) where i < j, and compute the GCD (greatest common divisor) of nums[i] and nums[j]. Collect all of these GCD values into one list, then sort that list in non-decreasing order.

You're also given a list of queries, where each query is an index into this sorted list of GCDs. For each query, return the GCD value sitting at that index.

The catch: nums can be large enough that the number of pairs is in the billions, so you cannot literally build this sorted list.

Example

Let's use nums = [2, 3, 4].

The three possible pairs are:

(2, 3) → GCD = 1
(2, 4) → GCD = 2
(3, 4) → GCD = 1

Collecting these GCDs gives [1, 2, 1]. Sorted, that becomes [1, 1, 2].

Now suppose queries = [0, 2]:

Query 0 asks for the smallest value → index 0 of [1, 1, 2] → 1
Query 2 asks for the last value → index 2 of [1, 1, 2] → 2

Simple to reason about with 3 numbers. The whole challenge is doing this same lookup when there are 100,000 numbers and the sorted list would have billions of entries.

Intuition

Here's how an experienced engineer approaches this once brute force is ruled out: stop thinking about individual pairs, and start thinking about divisors.

Ask a different question: for a given value g, how many pairs in nums have a GCD that is exactly g? If you can answer that for every possible g, you know the full shape of the sorted list without ever building it — you know "there are X copies of 1, Y copies of 2, Z copies of 3," and so on. That's enough to answer any index query with a prefix sum and a binary search.

So how do you count pairs with GCD exactly g, without checking every pair? Break it into two easier questions:

How many numbers in nums are multiples of g? Call this count c. Any two of these c numbers share g as a common divisor (not necessarily the greatest one, just a common divisor). So c choose 2 is the number of pairs whose GCD is a multiple of g — could be g, 2g, 3g, etc.
Subtract the pairs that belong to bigger multiples. If you already know exactly how many pairs have GCD 2g, 3g, 4g, ... (all multiples of g larger than g itself), subtract those off. What remains is pairs whose GCD is exactly g.

This only works if you process g from largest to smallest — by the time you need to subtract off the exact counts for 2g, 3g, etc., you must have already computed them.

Once you have "exact count of pairs for every GCD value," a prefix sum turns that into "how many pairs have GCD ≤ this value," and answering a query becomes a single binary search: find the first value where the running total passes the query index.

A quick self-check, the kind that clarifies whether you actually understand the trick: for nums = [2, 2], there's exactly one pair, and query = [0]. What's the answer?

The GCD of 2 and 2 is 2. So the exact count at g = 2 is 1, and everything else is 0. The prefix sum crosses index 0 right at value 2. The answer is 2 — and notice there was no special-casing for duplicate values. They just fall out of the same machinery.

Brute Force Solution

Idea: Compute the GCD of every pair, collect them into a list, sort it, and answer each query by direct indexing.

Algorithm:

For every i < j, compute gcd(nums[i], nums[j]) and append it to a list.
Sort the list.
For each query, return list[query].

Advantages:

Trivial to write and obviously correct — great as an opening answer in an interview to show you understand the problem.
No number-theory insight required.

Disadvantages:

With n = 100,000, the number of pairs is n*(n-1)/2 ≈ 5,000,000,000 — this will not fit in memory, let alone finish in reasonable time.

Complexity: O(n²) time to generate and compute all pairs, O(n²) space to store them, plus O(n² log n²) to sort. Fine for n in the hundreds; hopeless at n = 100,000.

Optimal Solution

Let M be the largest value in nums. The approach has four stages:

Step 1 — Tally the numbers. Build a frequency array freq of size M + 1, where freq[v] is how many times value v appears in nums. This compresses the entire input into counts — we no longer care about which numbers appear, only how many of each.

Step 2 — Count pairs divisible by each g. For every g from 1 to M, sweep its multiples (g, 2g, 3g, ...) and sum freq[g] + freq[2g] + freq[3g] + ... to get multiple_count[g] — the total count of numbers divisible by g. Then divisible_by_g_pairs = multiple_count[g] * (multiple_count[g] - 1) // 2. This is the classic "harmonic series" sieve — the total work across all g is O(M log M), not O(M²).

Step 3 — Peel out the exact GCDs. Walk g from M down to 1. For each g, subtract the already-known exact pair counts at 2g, 3g, 4g, ... from divisible_by_g_pairs. What's left is exact[g] — the number of pairs whose GCD is precisely g.

Step 4 — Prefix sum and answer queries. Build a prefix sum array prefix[g] = exact[1] + exact[2] + ... + exact[g] — the count of GCDs that are ≤ g. To answer a query index q, binary search for the smallest g such that prefix[g] > q. That g is the answer.

Stage	What it computes	Complexity
Tally	Count of each value	O(n + M)
Sieve	Pairs divisible by each g	O(M log M)
Peel	Exact GCD counts	O(M log M)
Prefix + query	Answer per query	O(M + Q log M)

Python Code

from bisect import bisect_right
from math import gcd
from typing import List


class Solution:
    def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:
        max_val = max(nums)

        # Step 1: tally how many times each value appears
        freq = [0] * (max_val + 1)
        for num in nums:
            freq[num] += 1

        # Step 2: count numbers divisible by each g (harmonic sieve)
        multiples_count = [0] * (max_val + 1)
        for g in range(1, max_val + 1):
            for multiple in range(g, max_val + 1, g):
                multiples_count[g] += freq[multiple]

        # Step 3: peel out exact GCD pair counts, largest g first
        exact_pairs = [0] * (max_val + 1)
        for g in range(max_val, 0, -1):
            total = multiples_count[g]
            pairs_divisible_by_g = total * (total - 1) // 2
            for multiple in range(2 * g, max_val + 1, g):
                pairs_divisible_by_g -= exact_pairs[multiple]
            exact_pairs[g] = pairs_divisible_by_g

        # Step 4: prefix sum over exact GCD counts
        prefix = []
        running_total = 0
        gcd_values = []  # gcd_values[i] corresponds to prefix[i]
        for g in range(1, max_val + 1):
            if exact_pairs[g] > 0:
                running_total += exact_pairs[g]
                prefix.append(running_total)
                gcd_values.append(g)

        # Answer each query with a binary search on the prefix sums
        answers = []
        for q in queries:
            idx = bisect_right(prefix, q)
            answers.append(gcd_values[idx])
        return answers

Code Walkthrough

max_val = max(nums) — we size every array around the largest value, since GCDs can never exceed it.
freq — a frequency array; freq[v] counts occurrences of v. This is the "squeeze the whole input into counts" step.
multiples_count[g] — for each g, we walk its multiples and sum how many input numbers land on them. This tells us how many numbers are divisible by g.
pairs_divisible_by_g = total * (total - 1) // 2 — the standard "n choose 2" formula, counting pairs among numbers divisible by g.
The inner loop for multiple in range(2 * g, max_val + 1, g) subtracts off exact counts already computed for larger multiples of g. Because we iterate g from high to low, those values are guaranteed to be ready.
exact_pairs[g] — what's left after subtraction: pairs whose GCD is precisely g.
prefix and gcd_values — we only record entries where exact_pairs[g] > 0, keeping the arrays compact; prefix[i] is the cumulative pair count up through gcd_values[i].
bisect_right(prefix, q) — finds the first index where the running total exceeds the query, which corresponds to the correct GCD value. We use bisect_right, not bisect_left, because a query index must land strictly inside the range covered by that GCD's count.

Dry Run

Take nums = [2, 3, 4], queries = [0, 2].

max_val = 4. freq = [0, 0, 1, 1, 1] (indices 0..4; freq[2]=1, freq[3]=1, freq[4]=1).
Sieve:
- g=1: multiples 1,2,3,4 → multiples_count[1] = 0+1+1+1 = 3
- g=2: multiples 2,4 → multiples_count[2] = 1+1 = 2
- g=3: multiples 3 → multiples_count[3] = 1
- g=4: multiples 4 → multiples_count[4] = 1
Peel, high to low:
- g=4: total=1 → pairs = 0 → exact_pairs[4]=0
- g=3: total=1 → pairs = 0 → exact_pairs[3]=0
- g=2: total=2 → pairs = 2*1/2=1; subtract multiples of 2 above 2 (only 4, which is 0) → exact_pairs[2]=1
- g=1: total=3 → pairs = 3*2/2=3; subtract exact_pairs[2]+exact_pairs[3]+exact_pairs[4] = 1+0+0=1 → exact_pairs[1]=2
Prefix: gcd_values=[1,2], prefix=[2,3] (2 pairs with GCD 1, then cumulative 3 after adding the 1 pair with GCD 2).
Queries:
- q=0: bisect_right([2,3], 0) = 0 → gcd_values[0] = 1 ✓ (matches expected)
- q=2: bisect_right([2,3], 2) = 1 → gcd_values[1] = 2 ✓ (matches expected)

Both match the sorted list [1, 1, 2] we built by hand earlier.

Complexity Analysis

Time: The sieve loop (for g: for multiple in range(g, max_val, g)) sums to M/1 + M/2 + M/3 + ... ≈ M log M — this is the harmonic series bound, and it runs twice (once for counting, once for peeling). Each query costs O(log M) for the binary search. Total: O(M log M + Q log M).
Space: freq, multiples_count, and exact_pairs are each O(M); prefix and gcd_values are at most O(M). Total: O(M).
Why this is correct: every pair is counted exactly once, at its true GCD — the sieve counts pairs divisible by g, and the high-to-low subtraction removes every pair that actually belongs to a larger multiple, leaving only pairs whose GCD is exactly g. No pair is double-counted or missed, because every pair's GCD is some divisor g of both elements, and we've enumerated every candidate g.

Alternative Solutions

You could skip the "peel exact GCDs" step and binary search directly on multiples_count-derived pair counts if you only needed "count of pairs with GCD divisible by X" queries — but this problem asks for exact GCD values at sorted positions, so peeling is required. There's no meaningfully different optimal approach here; the divisor-sieve is the standard technique for this problem shape, and the brute force is the only real alternative, useful purely as a starting point in discussion.

Edge Cases

All identical values (e.g., [2, 2, 2]): duplicates just inflate freq, and n choose 2 naturally counts pairs of identical numbers — no special casing needed.
Two elements only: the smallest valid input; still produces exactly one pair and one non-zero exact_pairs entry.
Values of 1 in the array: any pair including a 1 has GCD 1, correctly captured since multiples_count[1] counts everything.
Maximum value array (nums sized near constraints): verifies the sieve's O(M log M) bound holds in practice — this is where brute force would already have failed.
Query at index 0 and the last valid index: boundary checks for the binary search — make sure bisect_right doesn't run off the end of prefix.

Common Mistakes

Building the actual list of pairs to sort and index — this is the brute-force trap that blows up memory on large inputs.
Using bisect_left instead of bisect_right on the prefix sums, which shifts every query answer by one position (a subtle off-by-one that only shows up under specific duplicate patterns).
Iterating g from low to high during the peeling step, which subtracts values that haven't been computed yet, silently producing wrong (often negative) counts.
Forgetting to size arrays to max(nums) and instead sizing them to len(nums), which breaks whenever values exceed the array length.
Recomputing multiples_count inside the peeling loop instead of precomputing it once, turning an O(M log M) solution back into something far slower.
Not handling the case where exact_pairs[g] is zero when building the compact prefix/gcd_values arrays, leading to incorrect binary search results if zero-count entries are included inconsistently.

Interview Questions

How would you extend this to answer "GCD greater than a given value" queries instead of index queries?
Can you adapt this approach if nums could contain very large values (say, up to 10^9) instead of a bounded small range?
What changes if you needed the LCM distribution instead of GCD?
How would you handle queries that arrive as a stream, rather than all at once?
Why does the sieve loop run in O(M log M) rather than O(M²)? Walk through the harmonic series argument.

Similar Problems

LeetCode 1447 — Simplified Fractions: shares GCD-based pairwise reasoning.
LeetCode 878 — Nth Magical Number: similar "count then binary search for the Nth" structure.
LeetCode 1201 — Ugly Number III: counting via inclusion-exclusion, same "count don't enumerate" philosophy.
LeetCode 2183 — Count Array Pairs Divisible by K: near-identical divisor-counting technique applied to a different pair condition.
LeetCode 952 — Largest Component Size by Common Factor: uses a similar sieve-over-divisors idea, applied to union-find instead of counting.

Key Takeaways

When a problem's naive solution explodes combinatorially, look for a way to count by category instead of enumerating instances. Here, instead of listing every pair, we counted pairs per divisor using a tally array and a harmonic sieve, peeled out exact values by working from largest to smallest, and used prefix sums to turn "find the value at this index" into a single binary search. This pattern — precompute a distribution, then answer queries in O(log M) — is worth internalizing, because it reappears constantly in systems that serve fast reads over data that changes slowly.

Watch the Video

For a visual walkthrough of every step — including the paused challenge and the reveal — check out the full video here: {LINK}

About the Series

This solution is part of the Daily Python LeetCode series, where each day brings one problem broken down from first principles — not just the code, but the reasoning that gets you there, so the pattern sticks the next time it shows up in a different disguise.

Call To Action

If this helped the problem click, subscribe on YouTube so tomorrow's problem shows up in your feed, and subscribe to the Substack for the written breakdown delivered straight to your inbox. Drop a comment with the approach you'd have tried first, and share this with anyone grinding through their interview prep — it helps more than you'd think.