Welcome to Subscribe On Youtube
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.
-
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; } }
-
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; } };
-
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]
-
func gcdValues(nums []int, queries []int64) (ans []int) { mx := slices.Max(nums) cnt := make([]int, mx+1) cntG := make([]int, mx+1) for _, x := range nums { cnt[x]++ } for i := mx; i > 0; i-- { var v int for j := i; j <= mx; j += i { v += cnt[j] cntG[i] -= cntG[j] } cntG[i] += v * (v - 1) / 2 } for i := 2; i <= mx; i++ { cntG[i] += cntG[i-1] } for _, q := range queries { ans = append(ans, sort.SearchInts(cntG, int(q)+1)) } return }