Show problems as
Classic problem #3312HardArrayHash TableMathBinary SearchCombinatoricsCountingNumber TheoryPrefix SumEuclidean AlgorithmGreatest Common Divisor

Sorted GCD Pair Queries

Real-world version: Gear Mesh Queries
Tracked in this browser only
Read Sorted GCD Pair Queries on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A workshop holds n gear blanks, and blank i has been cut with teeth[i] teeth. For every pair of different blanks i < j, the mesh of that pair is the largest whole number that divides both teeth[i] and teeth[j].

All n * (n - 1) / 2 meshes are written on a card and the card is then sorted into non-decreasing order. Two different pairs that share a mesh value each contribute their own entry, so the card always holds exactly n * (n - 1) / 2 entries.

Answer the batch of queries against that sorted card: for each queries[t] return the entry at position queries[t], counting positions from 0. Return the answers in the order the queries were asked.

Examples

Example 1

Input
teeth = [2, 3, 4], queries = [0, 1, 2]
Output
[1, 1, 2]

The three pairs mesh at 1, 2 and 1, so the sorted card reads 1, 1, 2 and the three queries read off its three positions in turn.

Example 2

Input
teeth = [12, 18, 24, 30], queries = [5, 0, 3, 3]
Output
[12, 6, 6, 6]

The six pairs mesh at 6, 12, 6, 6, 6 and 6, so the sorted card reads 6, 6, 6, 6, 6, 12. Position 5 holds 12, position 0 holds 6, and position 3 is asked twice and holds 6 both times.

Example 3

Input
teeth = [50000, 25000, 2], queries = [0, 1, 2]
Output
[2, 2, 25000]

The pair of large blanks meshes at 25000 and both pairs involving the small blank mesh at 2, so the sorted card reads 2, 2, 25000.

Constraints

  • 2 <= n == teeth.length <= 10^5
  • 1 <= teeth[i] <= 5 * 10^4
  • 1 <= queries.length <= 10^5
  • 0 <= queries[t] < n * (n - 1) / 2

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def mesh_queries(teeth: list[int], queries: list[int]) -> list[int]:
Java
public int[] meshQueries(int[] teeth, long[] queries)

More on the same topics