LeetCode Solutions Blog

Sorted GCD Pair Queries

Number: 3583

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an integer array nums and a list of queries, for every possible pair (nums[i], nums[j]) with i < j compute the greatest common divisor (GCD). After sorting all these GCD values in ascending order, return for each query the element at the provided index in the sorted GCD pairs array.

Key Insights

Directly computing all pairs is infeasible due to the potential 10^5 numbers leading to nearly 5e10 pairs.
Use a frequency array to count occurrences of each number.
For each potential divisor d, compute the total count of numbers in nums that are divisible by d, then determine the total pairs having a gcd that is a multiple of d.
Utilize inclusion‐exclusion (or Mobius inversion style subtraction) to refine counts so that exactly those pairs whose GCD equals d are obtained.
Aggregate counts for each d and then, since lower d values come first in the sorted order, build a cumulative frequency mapping to answer queries with binary search.

Space and Time Complexity

Time Complexity: O(m log m) where m is the maximum value in nums (up to 5 * 10^4) due to iterating over divisors and their multiples. Space Complexity: O(m) for frequency and count arrays.

Solution

We first count the frequency of every number in nums. For every candidate divisor d (from the maximum possible value down to 1), we sum the counts of its multiples to find how many numbers are divisible by d. The number of pairs with both numbers divisible by d is computed using combinatorics. However, these counts include pairs whose actual gcd is a multiple of d. We subtract the contributions from higher multiples of d to extract exactly the count for gcd equal to d. Finally, we prepare a cumulative frequency (or prefix sum) over these gcd counts (ordered in ascending order) to answer each query in O(log m) using binary search.

Code Solutions

# Python solution with line-by-line comments
def sortedGcdPairQueries(nums, queries):
    # maximum value in nums (given constraint max <= 5e4)
    max_val = max(nums)
    size = max_val + 1
    
    # Frequency count of each number in nums
    freq = [0] * size
    for num in nums:
        freq[num] += 1
    
    # Array to store count of pairs with gcd exactly equal to index
    exact_gcd_count = [0] * size

    # For each d, count pairs among numbers divisible by d
    # Iterate d from max_val down to 1
    for d in range(max_val, 0, -1):
        tot = 0
        # Count how many numbers are divisible by d
        for multiple in range(d, size, d):
            tot += freq[multiple]
        # Total pairs with both numbers divisible by d
        pair_count = tot * (tot - 1) // 2
        # Subtract pairs counted for higher multiples of d (inclusion-exclusion)
        m = 2 * d
        while m < size:
            pair_count -= exact_gcd_count[m]
            m += d
        exact_gcd_count[d] = pair_count

    # Build sorted representation of gcd values with counts.
    # For ascending order, only gcd values that appear, along with a cumulative count.
    sorted_gcds = []
    for d in range(1, size):
        count = exact_gcd_count[d]
        if count > 0:
            sorted_gcds.append((d, count))
    
    # Build prefix sums over the counts for binary search queries.
    prefix = []
    cum = 0
    for g, count in sorted_gcds:
        cum += count
        prefix.append((cum, g))  # store tuple of (cumulative frequency, gcd value)
    
    # Answers to each query - using binary search on the prefix list
    from bisect import bisect_left
    answer = []
    for q in queries:
        # binary search for the first prefix index with cumulative frequency > q
        idx = bisect_left(prefix, (q + 1, 0))
        answer.append(prefix[idx][1])
    return answer

# Example usage:
if __name__ == "__main__":
    # Test Example 1
    nums = [2, 3, 4]
    queries = [0, 2, 2]
    print(sortedGcdPairQueries(nums, queries))  # Expected output: [1, 2, 2]