3312. Sorted GCD Pair Queries
Description
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
Solutions
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.
Let $\textit{mx}$ denote the maximum value in the array $\textit{nums}$, and let $\textit{cnt}$ record the occurrence count of each number in the array $\textit{nums}$. Let $\textit{cntG}[i]$ denote the number of pairs in the array $\textit{nums}$ whose GCD is equal to $i$. To calculate $\textit{cntG}[i]$, we can follow these steps:
- Calculate the occurrence count $v$ of multiples of $i$ in the array $\textit{nums}$. Then, the number of pairs formed by any two elements from these multiples must have a GCD that is a multiple of $i$, i.e., $\textit{cntG}[i]$ needs to be increased by $v \times (v - 1) / 2$;
- We need to exclude pairs whose GCD is a multiple of $i$ and greater than $i$. Therefore, for multiples $j$ of $i$, we need to subtract $\textit{cntG}[j]$.
The above steps require us to traverse $i$ from large to small so that when calculating $\textit{cntG}[i]$, we have already calculated all $\textit{cntG}[j]$.
Finally, we calculate the prefix sum of the array $\textit{cntG}$, and 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.
The time complexity is $O(n + (M + q) \times \log M)$, and the space complexity is $O(M)$. Here, $n$ and $M$ represent the length and the maximum value of the array $\textit{nums}$, respectively, and $q$ represents the number of queries.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|