Sorted GCD Pair Queries
HardPrompt
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 <= 1051 <= nums[i] <= 5 * 1041 <= queries.length <= 1050 <= queries[i] < n * (n - 1) / 2
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Create an empty list,
gcdPairs, to store the GCD of each pair. - Iterate through all possible pairs of indices
(i, j)where0 <= i < j < n. - For each pair, calculate the greatest common divisor (GCD) of
nums[i]andnums[j]. - Add the calculated GCD to the
gcdPairslist. - After iterating through all pairs, sort the
gcdPairslist in ascending order. - Create an
answerarray of the same size asqueries. - For each query
kinqueries, retrieve the element at indexkfrom the sortedgcdPairslist and store it in theanswerarray. - Return the
answerarray.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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). Givenncan be up to10^5,n^2is10^10, which is computationally infeasible.Memory Limit Exceeded: The space required to store all GCD pairs is
O(n^2). Forn = 10^5, this would require an astronomical amount of memory.
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.
Algorithm
- Find the maximum value
Min thenumsarray. - Create a frequency array
freqof sizeM+1to count occurrences of each number innums. - Create an array
multiplesOfof sizeM+1. For eachgfrom 1 toM, calculatemultiplesOf[g], the total count of numbers innumsthat are multiples ofg. This can be done efficiently using a sieve-like method inO(M log M)time. - Let
C[g]be the number of pairs(nums[i], nums[j])where both numbers are multiples ofg. This can be calculated asC[g] = multiplesOf[g] * (multiplesOf[g] - 1) / 2. - Let
countEq[g]be the number of pairs with GCD exactly equal tog. Using the principle of inclusion-exclusion, we can compute this. We knowC[g] = countEq[g] + countEq[2g] + countEq[3g] + .... By iteratinggfromMdown to 1, we can computecountEq[g] = C[g] - (countEq[2g] + countEq[3g] + ...). - Create a prefix sum array
prefixCountfromcountEq.prefixCount[g]will store the total number of pairs with GCD less than or equal tog. - For each query
k, perform a binary search on theprefixCountarray to find the smallestgsuch thatprefixCount[g] > k. Thisgis the answer for the query.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.