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.
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; }}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.