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 <= 1051 <= nums[i] <= 5 * 1041 <= queries.length <= 1050 <= queries[i] < n * (n - 1) / 2
Solutions
A GCD problem that doesn't even use the GCD function: i.e. a problem for mathematicians.
/**
* @param {number[]} nums
* @param {number[]} queries
* @return {number[]}
*/
var gcdValues = function (nums, queries) {
const m = Math.max(...nums);
const cnt = new Array(m + 1).fill(0);
for (const num of nums) {
cnt[num]++;
}
for (let i = 1; i <= m; i++) {
for (let j = i * 2; j <= m; j += i) {
cnt[i] += cnt[j];
}
}
for (let i = 1; i <= m; i++) {
cnt[i] = Math.floor((cnt[i] * (cnt[i] - 1)) / 2);
}
for (let i = m; i >= 1; i--) {
for (let j = i * 2; j <= m; j += i) {
cnt[i] -= cnt[j];
}
}
for (let i = 1; i <= m; i++) {
cnt[i] += cnt[i - 1];
}
const ans = [];
for (let q of queries) {
q++;
let left = 1,
right = m;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (cnt[mid] >= q) {
right = mid;
} else {
left = mid + 1;
}
}
ans.push(left);
}
return ans;
};