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 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: Prefix Sum + Binary Search

• Time complexity: O(nlog(Max(nums)))
• Space complexity: O(Max(nums))

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number[]} queries
 * @return {number[]}
 */
const gcdValues = function (nums, queries) {
  const maxNum = Math.max(...nums);
  const countDivisor = Array.from({ length: maxNum + 1 }, () => 0);
  const countGcdPair = Array.from({ length: maxNum + 1 }, () => 0);
  const prefixCountGcdPair = [0];

  for (const num of nums) {
    for (let divisor = 1; divisor * divisor <= num; divisor++) {
      if (num % divisor) continue;

      countDivisor[divisor] += 1;

      if (num / divisor !== divisor) {
        countDivisor[num / divisor] += 1;
      }
    }
  }

  for (let gcd = maxNum; gcd >= 1; gcd--) {
    const count = countDivisor[gcd];

    countGcdPair[gcd] = (count * (count - 1)) / 2;

    for (let largeGcd = gcd * 2; largeGcd <= maxNum; largeGcd += gcd) {
      countGcdPair[gcd] -= countGcdPair[largeGcd];
    }
  }

  for (let gcd = 1; gcd <= maxNum; gcd++) {
    const count = prefixCountGcdPair[gcd - 1] + countGcdPair[gcd];

    prefixCountGcdPair.push(count);
  }

  const findGcdPair = nth => {
    let left = 1;
    let right = prefixCountGcdPair.length - 1;

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);

      prefixCountGcdPair[mid] < nth ? (left = mid + 1) : (right = mid - 1);
    }

    return left;
  };

  return queries.map(index => findGcdPair(index + 1));
};