Tap here to switch tabs
Problem
Submissions

Problem: Sorted GCD Pair Queries

Sorted GCD Pair Queries asks you to find greatest common divisors for every distinct pair of array values, sort those results, and answer queries by returning the value at each requested position.

Statement

You are given an integer array nums of length n and an integer array queries.

Consider all pairs of indices (i, j) such that 0≤i<j<n0 \leq i < j < n. For each pair, compute the greatest common divisor of nums[i] and nums[j]. Collect all of these values into an array gcdPairs and sort it in ascending order.

For each query queries[i], find the value located at index queries[i] in the sorted gcdPairs array.

Return an array of integers containing the answer to each query in queries.

Constraints:

  • 2≤n==2 \leq n == nums.length ≤105\leq 10^5

  • 1≤1 \leq nums[i] ≤5imes104\leq 5 imes 10^4

  • 1≤1 \leq queries.length ≤105\leq 10^5

  • 0≤0 \leq queries[i] <nimes(n−1)2< \frac{n imes (n - 1)}{2}

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Sorted GCD Pair Queries

Sorted GCD Pair Queries asks you to find greatest common divisors for every distinct pair of array values, sort those results, and answer queries by returning the value at each requested position.

Statement

You are given an integer array nums of length n and an integer array queries.

Consider all pairs of indices (i, j) such that 0≤i<j<n0 \leq i < j < n. For each pair, compute the greatest common divisor of nums[i] and nums[j]. Collect all of these values into an array gcdPairs and sort it in ascending order.

For each query queries[i], find the value located at index queries[i] in the sorted gcdPairs array.

Return an array of integers containing the answer to each query in queries.

Constraints:

  • 2≤n==2 \leq n == nums.length ≤105\leq 10^5

  • 1≤1 \leq nums[i] ≤5imes104\leq 5 imes 10^4

  • 1≤1 \leq queries.length ≤105\leq 10^5

  • 0≤0 \leq queries[i] <nimes(n−1)2< \frac{n imes (n - 1)}{2}