How do you solve Sorted GCD Pair Queries on LeetCode?

Sorted GCD Pair Queries (LeetCode #3312) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Counting pairs with specific GCDs can significantly reduce computation time.

What is the brute force solution for Sorted GCD Pair Queries?

The brute force approach for Sorted GCD Pair Queries is Brute Force, with O(n²) time complexity and O(n²) space complexity. The brute force approach calculates the GCD for every possible pair of elements in the array. This is straightforward but inefficient for large inputs, as it requires checking all combinations. The optimal Optimal Solution approach improves this to O(n log n).

What are the interview tips for Sorted GCD Pair Queries?

Always clarify the constraints and edge cases before diving into coding. Think about the efficiency of your approach and how you can optimize it. Practice explaining your thought process clearly as you code.

What are common mistakes when solving Sorted GCD Pair Queries?

Failing to consider the maximum value in nums when counting GCDs. Not using the inclusion-exclusion principle correctly.

#3312

Sorted GCD Pair Queries

Hard

ArrayHash TableMathBinary SearchCombinatoricsCountingNumber TheoryPrefix SumHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(n²)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

Instead of generating all pairs, we can count how many pairs have a specific GCD using a frequency array and the inclusion-exclusion principle. This allows us to efficiently compute the sorted GCD values.

⚙️

Algorithm

5 steps

1Step 1: Create a frequency array to count occurrences of each number in nums.
2Step 2: For each possible GCD from 1 to the maximum number in nums, calculate how many pairs have that GCD using the frequency array.
3Step 3: Use the inclusion-exclusion principle to count pairs for each GCD value.
4Step 4: Store the counts of pairs for each GCD in a sorted list.
5Step 5: For each query, retrieve the value at the specified index from the sorted list.

solution.py21 lines

1# Full working Python code
2import math
3from collections import Counter
4
5
6def gcd_pairs(nums, queries):
7    max_num = max(nums)
8    freq = Counter(nums)
9    gcd_count = [0] * (max_num + 1)
10    
11    for g in range(1, max_num + 1):
12        count = 0
13        for multiple in range(g, max_num + 1, g):
14            count += freq[multiple]
15        gcd_count[g] = count * (count - 1) // 2
16    
17    sorted_gcds = []
18    for g in range(1, max_num + 1):
19        sorted_gcds.extend([g] * gcd_count[g])
20    
21    return [sorted_gcds[q] for q in queries]

ℹ

Complexity note: The time complexity is O(n log n) due to the sorting step and the counting of pairs. The space complexity is O(n) for storing the frequency and GCD counts.

1Counting pairs with specific GCDs can significantly reduce computation time.
2Using frequency arrays allows for efficient pair counting.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.