# Sorted GCD Pair Queries
**Difficulty:** HARD
[External](https://leetcode.com/problems/sorted-gcd-pair-queries)
Canonical: https://scaleengineer.com/dsa/problems/sorted-gcd-pair-queries
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Counting](https://scaleengineer.com/dsa/patterns/counting), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table
---
## Problem
You are given an integer array `nums` of length `n` and an integer array `queries`.

Let `gcdPairs` denote an array obtained by calculating the GCD of all possible pairs `(nums[i], nums[j])`, where `0 <= i < j < n`, and then sorting these values in **ascending** order.

For each query `queries[i]`, you need to find the element at index `queries[i]` in `gcdPairs`.

Return an integer array `answer`, where `answer[i]` is the value at `gcdPairs[queries[i]]` for each query.

The term `gcd(a, b)` denotes the **greatest common divisor** of `a` and `b`.

**Example 1:**

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

**Output:** \[1,2,2\]

**Explanation:**

`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\]

**Explanation:**

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

**Example 3:**

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

**Output:** \[2,2\]

**Explanation:**

`gcdPairs = [2]`.

**Constraints:**

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

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem statement. It involves generating every possible pair of numbers from the input array, calculating their GCD, storing all these GCDs, sorting them, and then picking the elements requested by the queries.
**Time:** O(n^2 log(max(nums)) + n^2 log(n^2)). Generating pairs and calculating GCDs takes `O(n^2 log(max(nums)))`. Sorting the `n * (n - 1) / 2` pairs takes `O(n^2 log(n^2))`, which simplifies to `O(n^2 log n)`. The sorting step dominates. · **Space:** O(n^2), where `n` is the length of `nums`. This is for storing the `gcdPairs` list, which contains `n * (n - 1) / 2` elements.
**Pros:** **Simplicity:** The logic is easy to understand and follows the problem description directly.; **Correctness:** For small inputs, this approach will produce the correct result.
**Cons:** **Time Limit Exceeded:** The time complexity is dominated by generating and sorting the pairs, which is `O(n^2 log n)`. Given `n` can be up to `10^5`, `n^2` is `10^10`, which is computationally infeasible.; **Memory Limit Exceeded:** The space required to store all GCD pairs is `O(n^2)`. For `n = 10^5`, this would require an astronomical amount of memory.
### Explanation
The most straightforward way to solve this problem is to follow the steps literally. We can use nested loops to form all unique pairs of elements from the `nums` array. For each pair, we compute their GCD using a standard algorithm like the Euclidean algorithm. These GCDs are collected into a list. Once all pairs have been processed, this list is sorted numerically. Finally, we iterate through the `queries` array, and for each query index, we look up the value at that position in our sorted list of GCDs. While simple, this method is highly inefficient for the given constraints.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    // Helper function to calculate GCD
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public int[] sortedGcdPairQueries(int[] nums, int[] queries) {
        int n = nums.length;
        List<Integer> gcdPairs = new ArrayList<>();

        // Step 1 & 2: Generate all pairs and compute GCD
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                gcdPairs.add(gcd(nums[i], nums[j]));
            }
        }

        // Step 3: Sort the list of GCDs
        Collections.sort(gcdPairs);

        // Step 4: Process queries
        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            answer[i] = gcdPairs.get(queries[i]);
        }

        return answer;
    }
}
```
### Algorithm
- Create an empty list, `gcdPairs`, to store the GCD of each pair.
- Iterate through all possible pairs of indices `(i, j)` where `0 <= i < j < n`.
- For each pair, calculate the greatest common divisor (GCD) of `nums[i]` and `nums[j]`.
- Add the calculated GCD to the `gcdPairs` list.
- After iterating through all pairs, sort the `gcdPairs` list in ascending order.
- Create an `answer` array of the same size as `queries`.
- For each query `k` in `queries`, retrieve the element at index `k` from the sorted `gcdPairs` list and store it in the `answer` array.
- Return the `answer` array.

## Pre-computation using Number Theory and Binary Search
Since the brute-force approach is too slow, we need a more efficient method. The key observation is that the number of pairs is huge, but the possible values for the GCDs are limited by the maximum value in `nums`. Instead of generating each GCD, we can count how many pairs result in each possible GCD value. This transforms the problem into a counting problem that can be solved with number theory and efficient pre-computation.
**Time:** O(n + M log M + Q log M), where `n` is `nums.length`, `M` is `max(nums)`, and `Q` is `queries.length`. `O(n+M)` for frequency counts, `O(M log M)` for pre-computation of counts, and `O(Q log M)` for processing all queries with binary search. · **Space:** O(M), where `M` is the maximum value in `nums`. We need several arrays of size `M+1` for pre-computation.
**Pros:** **Highly Efficient:** This approach is fast enough to pass within the time limits for the given constraints.; **Memory Efficient:** The space complexity is linear with respect to the maximum value in `nums`, not the number of pairs.
**Cons:** **Complexity:** The algorithm is significantly more complex to understand and implement compared to the brute-force approach.; **Requires Number Theory:** The solution relies on understanding GCD properties and the principle of inclusion-exclusion.
### Explanation
This approach hinges on efficiently counting, for each integer `g`, the number of pairs `(nums[i], nums[j])` such that `gcd(nums[i], nums[j]) = g`. Let's call this `countEq[g]`.

First, we pre-process the input `nums`. We find the maximum value `M` and create a frequency count of all numbers. Then, we compute an array `multiplesOf`, where `multiplesOf[g]` stores how many numbers in `nums` are multiples of `g`. This can be done in `O(M log M)` time.

With `multiplesOf[g]`, we can easily find `C[g]`, the number of pairs whose GCD is a *multiple* of `g`. This is simply the number of ways to choose 2 elements from the `multiplesOf[g]` available numbers, which is `multiplesOf[g] * (multiplesOf[g] - 1) / 2`.

The crucial step is to find `countEq[g]` from `C[g]`. A pair whose GCD is a multiple of `g` could have a GCD of `g`, `2g`, `3g`, etc. So, `C[g] = countEq[g] + countEq[2g] + countEq[3g] + ...`. We can rearrange this to `countEq[g] = C[g] - (countEq[2g] + countEq[3g] + ...)`. By iterating `g` from `M` down to 1, we can calculate all `countEq[g]` values, as the terms on the right-hand side will have already been computed.

After computing `countEq` for all `g` from 1 to `M`, we effectively have the counts of each value in the sorted `gcdPairs` array. We build a prefix sum array on `countEq`. For a query `k`, we can then use binary search on this prefix sum array to find which GCD value corresponds to the `k`-th position in `O(log M)` time.

```java
import java.util.Arrays;

class Solution {
    public int[] sortedGcdPairQueries(int[] nums, int[] queries) {
        int maxNum = 0;
        for (int num : nums) {
            if (num > maxNum) {
                maxNum = num;
            }
        }

        int[] freq = new int[maxNum + 1];
        for (int num : nums) {
            freq[num]++;
        }

        long[] multiplesOf = new long[maxNum + 1];
        for (int g = 1; g <= maxNum; g++) {
            for (int multiple = g; multiple <= maxNum; multiple += g) {
                multiplesOf[g] += freq[multiple];
            }
        }

        long[] C = new long[maxNum + 1];
        for (int g = 1; g <= maxNum; g++) {
            C[g] = multiplesOf[g] * (multiplesOf[g] - 1) / 2;
        }

        long[] countEq = new long[maxNum + 1];
        for (int g = maxNum; g >= 1; g--) {
            countEq[g] = C[g];
            for (int multiple = 2 * g; multiple <= maxNum; multiple += g) {
                countEq[g] -= countEq[multiple];
            }
        }

        long[] prefixCount = new long[maxNum + 1];
        for (int g = 1; g <= maxNum; g++) {
            prefixCount[g] = prefixCount[g - 1] + countEq[g];
        }

        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            long k = queries[i];
            int low = 1, high = maxNum, res = 0;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (prefixCount[mid] > k) {
                    res = mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            answer[i] = res;
        }

        return answer;
    }
}
```
### Algorithm
- Find the maximum value `M` in the `nums` array.
- Create a frequency array `freq` of size `M+1` to count occurrences of each number in `nums`.
- Create an array `multiplesOf` of size `M+1`. For each `g` from 1 to `M`, calculate `multiplesOf[g]`, the total count of numbers in `nums` that are multiples of `g`. This can be done efficiently using a sieve-like method in `O(M log M)` time.
- Let `C[g]` be the number of pairs `(nums[i], nums[j])` where both numbers are multiples of `g`. This can be calculated as `C[g] = multiplesOf[g] * (multiplesOf[g] - 1) / 2`.
- Let `countEq[g]` be the number of pairs with GCD exactly equal to `g`. Using the principle of inclusion-exclusion, we can compute this. We know `C[g] = countEq[g] + countEq[2g] + countEq[3g] + ...`. By iterating `g` from `M` down to 1, we can compute `countEq[g] = C[g] - (countEq[2g] + countEq[3g] + ...)`.
- Create a prefix sum array `prefixCount` from `countEq`. `prefixCount[g]` will store the total number of pairs with GCD less than or equal to `g`.
- For each query `k`, perform a binary search on the `prefixCount` array to find the smallest `g` such that `prefixCount[g] > k`. This `g` is the answer for the query.

# Solutions
### Java

```java
class Solution {
public
  int[] gcdValues(int[] nums, long[] queries) {
    int mx = Arrays.stream(nums).max().getAsInt();
    int[] cnt = new int[mx + 1];
    long[] cntG = new long[mx + 1];
    for (int x : nums) {
      ++cnt[x];
    }
    for (int i = mx; i > 0; --i) {
      int v = 0;
      for (int j = i; j <= mx; j += i) {
        v += cnt[j];
        cntG[i] -= cntG[j];
      }
      cntG[i] += 1L * v * (v - 1) / 2;
    }
    for (int i = 2; i <= mx; ++i) {
      cntG[i] += cntG[i - 1];
    }
    int m = queries.length;
    int[] ans = new int[m];
    for (int i = 0; i < m; ++i) {
      ans[i] = search(cntG, queries[i]);
    }
    return ans;
  }
private
  int search(long[] nums, long x) {
    int n = nums.length;
    int l = 0, r = n;
    while (l < r) {
      int mid = l + r >> 1;
      if (nums[mid] > x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> gcdValues(vector<int> &nums, vector<long long> &queries) {
    int mx = ranges ::max(nums);
    vector<int> cnt(mx + 1);
    vector<long long> cntG(mx + 1);
    for (int x : nums) {
      ++cnt[x];
    }
    for (int i = mx; i; --i) {
      long long v = 0;
      for (int j = i; j <= mx; j += i) {
        v += cnt[j];
        cntG[i] -= cntG[j];
      }
      cntG[i] += 1LL * v * (v - 1) / 2;
    }
    for (int i = 2; i <= mx; ++i) {
      cntG[i] += cntG[i - 1];
    }
    vector<int> ans;
    for (auto &&q : queries) {
      ans.push_back(upper_bound(cntG.begin(), cntG.end(), q) - cntG.begin());
    }
    return ans;
  }
};

```

### Python

```python
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]

```