#3312

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Sorted GCD Pair Queries

Solve the Sorted GCD Pair Queries problem by efficiently counting and locating GCDs of all array pairs using hash mapping.

array hash table math binary search combinatorics

Problem Statement

You are given an integer array nums of length n and a queries array. Compute all possible GCDs for each pair (nums[i], nums[j]) where 0 <= i < j < n, then sort these GCDs in ascending order.

For each index in queries, return the GCD at that position from the sorted list. Ensure the solution efficiently handles large arrays without explicitly generating every pair, leveraging counting and hash-based strategies.

Examples

Example 1

Input: nums = [2,3,4], queries = [0,2,2]

Output: [1,2,2]

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]

gcdPairs sorted in ascending order is [1, 1, 1, 2, 2, 4] .

Example 3

Input: nums = [2,2], queries = [0,0]

Output: [2,2]

gcdPairs = [2] .

Constraints

2 <= n == nums.length <= 105
1 <= nums[i] <= 5 * 104
1 <= queries.length <= 105
0 <= queries[i] < n * (n - 1) / 2

Solution Approach

Count GCD Frequencies Using Hash Map

Iterate through nums and count occurrences of each number. For each possible GCD g, calculate how many pairs produce g using combinatorial formulas and store results in a hash table for quick access.

Generate Sorted GCD Prefix Sum

Convert the hash map of GCD counts into a prefix sum array representing the cumulative number of pairs up to each GCD value. This allows fast lookup for the query indices without sorting all pairs explicitly.

Answer Queries with Binary Search

For each query index, perform a binary search on the prefix sum array to locate the GCD corresponding to that index. This efficiently resolves all queries in O(log M) per query, where M is the number of distinct GCDs.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of distinct GCDs and the prefix sum processing, typically O(N log N + Q log M). Space complexity is O(M) for storing GCD counts and prefix sums.

What Interviewers Usually Probe

The candidate considers counting pairs instead of brute-force pair generation.
Mentions using hash maps to store GCD frequencies for fast queries.
Uses prefix sums or cumulative counts to answer multiple queries efficiently.

Common Pitfalls or Variants

Common pitfalls

Attempting to generate all pairs explicitly, which leads to memory overflow on large arrays.
Ignoring duplicates in nums, which affects the correct pair count for GCDs.
Not using cumulative counts, resulting in O(N^2) query lookups.

Follow-up variants

Return the k-th largest GCD instead of the k-th smallest.
Handle dynamic updates to nums and answer queries in real time.
Count pairs with GCD divisible by a given integer instead of exact GCD values.

FAQ

What is the primary pattern in Sorted GCD Pair Queries?

The pattern is array scanning plus hash lookup to count GCDs efficiently without enumerating all pairs.

Can I solve this problem by generating all pairs?

Generating all pairs is feasible only for small arrays; the recommended method uses counting and hash maps to scale.

How does prefix sum help answer queries quickly?

Prefix sums accumulate pair counts for each GCD, enabling direct index-based lookup via binary search instead of scanning all pairs.

Do duplicate numbers in nums affect results?

Yes, duplicates increase the number of pairs with the same GCD, which must be correctly counted to answer queries accurately.

What is an efficient approach to large query arrays?

Use the hash table to store GCD counts and prefix sums to resolve each query in O(log M) time, avoiding explicit pair iteration.

terminal

Solution

Solution 1: 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 $\textit{nums}$, recorded in the array $\textit{cntG}$. Then, we calculate the prefix sum of the array $\textit{cntG}$. Finally, for each query, we can use binary search to find the index of the first element in the array $\textit{cntG}$ that is greater than $\textit{queries}[i]$, which is the answer.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:
        mx = max(nums)
        cnt = Counter(nums)
        cnt_g = [0] * (mx + 1)
        for i in range(mx, 0, -1):
            v = 0
            for j in range(i, mx + 1, i):
                v += cnt[j]
                cnt_g[i] -= cnt_g[j]
            cnt_g[i] += v * (v - 1) // 2
        s = list(accumulate(cnt_g))
        return [bisect_right(s, q) for q in queries]

Continue Practicing

#3128 right triangles #3116 kth smallest amount with single denomination combination #3044 most frequent prime