DDSA Solutions

3312. Sorted GCD Pair Queries

HardView on LeetCode
ArrayHash TableMathBinary SearchNumber TheoryCounting

Problem Overview

The GCD of any pair is at most max(nums), so count pairs by their exact GCD instead of generating and sorting all O(n²) pair values.

Intuition

The GCD of any pair is at most max(nums), so count pairs by their exact GCD instead of generating and sorting all O(n²) pair values. If c[d] numbers are divisible by d, then C(c[d], 2) pairs have a GCD that is a multiple of d. Processing d from large to small lets us subtract counts already assigned to 2d, 3d, and so on, leaving only pairs whose GCD is exactly d.

Algorithm

  1. 1Let M = max(nums). For every number, enumerate its divisors in O(√num) and increment countDivisor[d] for each divisor d.
  2. 2For gcd from M down to 1, start countGcdPair[gcd] at C(countDivisor[gcd], 2).
  3. 3Subtract countGcdPair[2·gcd], countGcdPair[3·gcd], … so only pairs with exact GCD gcd remain.
  4. 4Build prefixCount[g] = number of pairs whose GCD is at most g. This represents the cumulative positions in the sorted list of all pair GCDs.
  5. 5For each zero-based query q, binary-search the first g with prefixCount[g] ≥ q+1 and return g.

Example Walkthrough

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

  1. 1.The three pairs have GCDs: gcd(2,3)=1, gcd(2,4)=2, and gcd(3,4)=1.
  2. 2.Their sorted GCD list is [1, 1, 2].
  3. 3.Exact counts are countGcdPair[1]=2 and countGcdPair[2]=1, so prefixCount[1]=2 and prefixCount[2]=3.
  4. 4.Query 0 is the first value, found at GCD 1; query 2 is the third value, found at GCD 2.

Output: [1, 2]

Common Pitfalls

  • •C(countDivisor[d], 2) includes every pair whose GCD is a multiple of d, not only pairs whose GCD equals d; subtract exact counts of larger multiples.
  • •Process possible GCDs from large to small so all larger-multiple counts are already known.
  • •Queries are zero-based, while prefix counts are cardinalities; search for query+1.
  • •Pair counts can be O(n²), so use long even though each returned GCD fits in int.
  • •Enumerate both divisors i and num/i, but count a square root only once.
3312.cs
C#
public class Solution
{
    // Approach: Count how many values are divisible by each possible divisor.
    // Process divisors from large to small and use inclusion-exclusion to obtain
    // the number of pairs whose GCD is exactly each divisor. Prefix those counts,
    // then binary-search the prefix array for every zero-based sorted-pair query.
    // Complexity: O(sum(sqrt(nums[i])) + M log M + Q log M) time and O(M + Q) space,
    // where M = max(nums) and Q = queries.Length.
    public int[] GcdValues(int[] nums, long[] queries)
    {
        int maxNum = nums.Max();
        int[] ans = new int[queries.Length];
        // countDivisor[d] := the number of `nums` having `num % d == 0`
        int[] countDivisor = new int[maxNum + 1];
        // countGcdPair[g] := the number of pairs having gcd == g
        long[] countGcdPair = new long[maxNum + 1];
        // prefixCountGcdPair[g] := the number of pairs having gcd <= g
        long[] prefixCountGcdPair = new long[maxNum + 1];

        foreach (int num in nums)
        {
            for (int i = 1; i * i <= num; ++i)
            {
                if (num % i == 0)
                {
                    countDivisor[i]++;
                    if (i != num / i)
                        countDivisor[num / i]++;
                }
            }
        }

        for (int gcd = maxNum; gcd >= 1; --gcd)
        {
            // There are C(countDivisor[gcd], 2) pairs that have a common divisor
            // that's a multiple of `gcd` (including the one that equals to `gcd`).
            // So, subtract the multiples of `gcd` to have the number of pairs with a
            // gcd that's exactly `gcd`.
            countGcdPair[gcd] = (long)countDivisor[gcd] * (countDivisor[gcd] - 1) / 2;
            for (int largerGcd = 2 * gcd; largerGcd <= maxNum; largerGcd += gcd)
                countGcdPair[gcd] -= countGcdPair[largerGcd];
        }

        for (int gcd = 1; gcd <= maxNum; ++gcd)
            prefixCountGcdPair[gcd] = prefixCountGcdPair[gcd - 1] + countGcdPair[gcd];

        for (int i = 0; i < queries.Length; ++i)
            ans[i] = GetNthGcdPair(queries[i], prefixCountGcdPair);

        return ans;
    }

    // Returns the `query`-th gcd pair.
    private int GetNthGcdPair(long query, long[] prefixCountGcdPair)
    {
        int l = 1;
        int r = prefixCountGcdPair.Length - 1;
        while (l < r)
        {
            int m = (l + r) / 2;
            if (prefixCountGcdPair[m] < query + 1)
                l = m + 1;
            else
                r = m;
        }
        return l;
    }
}
Was this solution helpful?

Related Problems