Sorted GCD Pair Queries

Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14



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

1
2
3
4
5
6
7
8



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

1
2
3
4
5
6
7
8



Input: nums = [2,2], queries = [0,0]

Output: [2,2]

Explanation:

`gcdPairs = [2]`.

Constraints

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

Solution

Method 1 - Counting with Möbius Function

Intuition: Instead of generating all O(n²) pairs, we count how many pairs have each possible GCD value. We use number theory (Möbius function) to efficiently count pairs with specific GCD values.

Approach:

Count frequency of each number in nums
For each possible GCD value g, count how many pairs have GCD exactly equal to g
Use inclusion-exclusion principle with Möbius function to avoid overcounting
Build prefix sum array to answer queries in O(1)
Use binary search to find the answer for each query

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {
    int maxVal = *max_element(nums.begin(), nums.end());
    
    // Count frequency of each number
    vector<int> freq(maxVal + 1, 0);
    for (int num : nums) {
        freq[num]++;
    }
    
    // Count how many numbers are divisible by each divisor
    vector<long long> divisorCount(maxVal + 1, 0);
    for (int d = 1; d <= maxVal; d++) {
        for (int multiple = d; multiple <= maxVal; multiple += d) {
            divisorCount[d] += freq[multiple];
        }
    }
    
    // Count pairs with GCD exactly equal to g using inclusion-exclusion
    vector<long long> gcdCount(maxVal + 1, 0);
    for (int g = maxVal; g >= 1; g--) {
        long long cnt = divisorCount[g];
        gcdCount[g] = cnt * (cnt - 1) / 2; // Choose 2 from cnt numbers
        
        // Subtract pairs with GCD > g (inclusion-exclusion)
        for (int multiple = 2 * g; multiple <= maxVal; multiple += g) {
            gcdCount[g] -= gcdCount[multiple];
        }
    }
    
    // Build prefix sum for binary search
    vector<long long> prefixSum;
    for (int g = 1; g <= maxVal; g++) {
        if (gcdCount[g] > 0) {
            for (long long i = 0; i < gcdCount[g]; i++) {
                prefixSum.push_back(g);
            }
        }
    }
    
    vector<int> result;
    for (long long query : queries) {
        result.push_back(prefixSum[query]);
    }
    
    return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50


import "sort"

func gcdValues(nums []int, queries []int64) []int {
    maxVal := 0
    for _, num := range nums {
        if num > maxVal {
            maxVal = num
        }
    }
    
    // Count frequency
    freq := make([]int, maxVal+1)
    for _, num := range nums {
        freq[num]++
    }
    
    // Count divisor occurrences
    divisorCount := make([]int64, maxVal+1)
    for d := 1; d <= maxVal; d++ {
        for multiple := d; multiple <= maxVal; multiple += d {
            divisorCount[d] += int64(freq[multiple])
        }
    }
    
    // Count GCD pairs using inclusion-exclusion
    gcdCount := make([]int64, maxVal+1)
    for g := maxVal; g >= 1; g-- {
        cnt := divisorCount[g]
        gcdCount[g] = cnt * (cnt - 1) / 2
        
        for multiple := 2 * g; multiple <= maxVal; multiple += g {
            gcdCount[g] -= gcdCount[multiple]
        }
    }
    
    // Build sorted list
    var prefixSum []int
    for g := 1; g <= maxVal; g++ {
        for i := int64(0); i < gcdCount[g]; i++ {
            prefixSum = append(prefixSum, g)
        }
    }
    
    result := make([]int, len(queries))
    for i, query := range queries {
        result[i] = prefixSum[query]
    }
    
    return result
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


import java.util.*;

class Solution {
    public int[] gcdValues(int[] nums, long[] queries) {
        int maxVal = Arrays.stream(nums).max().getAsInt();
        
        // Count frequency
        int[] freq = new int[maxVal + 1];
        for (int num : nums) {
            freq[num]++;
        }
        
        // Count divisor occurrences
        long[] divisorCount = new long[maxVal + 1];
        for (int d = 1; d <= maxVal; d++) {
            for (int multiple = d; multiple <= maxVal; multiple += d) {
                divisorCount[d] += freq[multiple];
            }
        }
        
        // Count GCD pairs using inclusion-exclusion
        long[] gcdCount = new long[maxVal + 1];
        for (int g = maxVal; g >= 1; g--) {
            long cnt = divisorCount[g];
            gcdCount[g] = cnt * (cnt - 1) / 2;
            
            for (int multiple = 2 * g; multiple <= maxVal; multiple += g) {
                gcdCount[g] -= gcdCount[multiple];
            }
        }
        
        // Build sorted list
        List<Integer> prefixSum = new ArrayList<>();
        for (int g = 1; g <= maxVal; g++) {
            for (long i = 0; i < gcdCount[g]; i++) {
                prefixSum.add(g);
            }
        }
        
        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            result[i] = prefixSum.get((int) queries[i]);
        }
        
        return result;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


class Solution {
    fun gcdValues(nums: IntArray, queries: LongArray): IntArray {
        val maxVal = nums.maxOrNull() ?: 0
        
        // Count frequency
        val freq = IntArray(maxVal + 1)
        for (num in nums) {
            freq[num]++
        }
        
        // Count divisor occurrences
        val divisorCount = LongArray(maxVal + 1)
        for (d in 1..maxVal) {
            var multiple = d
            while (multiple <= maxVal) {
                divisorCount[d] += freq[multiple].toLong()
                multiple += d
            }
        }
        
        // Count GCD pairs using inclusion-exclusion
        val gcdCount = LongArray(maxVal + 1)
        for (g in maxVal downTo 1) {
            val cnt = divisorCount[g]
            gcdCount[g] = cnt * (cnt - 1) / 2
            
            var multiple = 2 * g
            while (multiple <= maxVal) {
                gcdCount[g] -= gcdCount[multiple]
                multiple += g
            }
        }
        
        // Build sorted list
        val prefixSum = mutableListOf<Int>()
        for (g in 1..maxVal) {
            repeat(gcdCount[g].toInt()) {
                prefixSum.add(g)
            }
        }
        
        return IntArray(queries.size) { i ->
            prefixSum[queries[i].toInt()]
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


def gcdValues(nums: list[int], queries: list[int]) -> list[int]:
    max_val = max(nums)
    
    # Count frequency
    freq = [0] * (max_val + 1)
    for num in nums:
        freq[num] += 1
    
    # Count divisor occurrences
    divisor_count = [0] * (max_val + 1)
    for d in range(1, max_val + 1):
        for multiple in range(d, max_val + 1, d):
            divisor_count[d] += freq[multiple]
    
    # Count GCD pairs using inclusion-exclusion
    gcd_count = [0] * (max_val + 1)
    for g in range(max_val, 0, -1):
        cnt = divisor_count[g]
        gcd_count[g] = cnt * (cnt - 1) // 2
        
        for multiple in range(2 * g, max_val + 1, g):
            gcd_count[g] -= gcd_count[multiple]
    
    # Build sorted list
    prefix_sum = []
    for g in range(1, max_val + 1):
        prefix_sum.extend([g] * gcd_count[g])
    
    return [prefix_sum[query] for query in queries]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


pub fn gcd_values(nums: Vec<i32>, queries: Vec<i64>) -> Vec<i32> {
    let max_val = *nums.iter().max().unwrap() as usize;
    
    // Count frequency
    let mut freq = vec![0; max_val + 1];
    for num in nums {
        freq[num as usize] += 1;
    }
    
    // Count divisor occurrences
    let mut divisor_count = vec![0i64; max_val + 1];
    for d in 1..=max_val {
        let mut multiple = d;
        while multiple <= max_val {
            divisor_count[d] += freq[multiple] as i64;
            multiple += d;
        }
    }
    
    // Count GCD pairs using inclusion-exclusion
    let mut gcd_count = vec![0i64; max_val + 1];
    for g in (1..=max_val).rev() {
        let cnt = divisor_count[g];
        gcd_count[g] = cnt * (cnt - 1) / 2;
        
        let mut multiple = 2 * g;
        while multiple <= max_val {
            gcd_count[g] -= gcd_count[multiple];
            multiple += g;
        }
    }
    
    // Build sorted list
    let mut prefix_sum = Vec::new();
    for g in 1..=max_val {
        for _ in 0..gcd_count[g] {
            prefix_sum.push(g as i32);
        }
    }
    
    queries.iter().map(|&query| prefix_sum[query as usize]).collect()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


function gcdValues(nums: number[], queries: number[]): number[] {
    const maxVal = Math.max(...nums);
    
    // Count frequency
    const freq = new Array(maxVal + 1).fill(0);
    for (const num of nums) {
        freq[num]++;
    }
    
    // Count divisor occurrences
    const divisorCount = new Array(maxVal + 1).fill(0);
    for (let d = 1; d <= maxVal; d++) {
        for (let multiple = d; multiple <= maxVal; multiple += d) {
            divisorCount[d] += freq[multiple];
        }
    }
    
    // Count GCD pairs using inclusion-exclusion
    const gcdCount = new Array(maxVal + 1).fill(0);
    for (let g = maxVal; g >= 1; g--) {
        const cnt = divisorCount[g];
        gcdCount[g] = Math.floor(cnt * (cnt - 1) / 2);
        
        for (let multiple = 2 * g; multiple <= maxVal; multiple += g) {
            gcdCount[g] -= gcdCount[multiple];
        }
    }
    
    // Build sorted list
    const prefixSum: number[] = [];
    for (let g = 1; g <= maxVal; g++) {
        for (let i = 0; i < gcdCount[g]; i++) {
            prefixSum.push(g);
        }
    }
    
    return queries.map(query => prefixSum[query]);
}

Complexity

⏰ Time complexity: O(M log M + Q) where M is the maximum value in nums and Q is the number of queries
🧺 Space complexity: O(M + P) where P is the total number of pairs

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 - Counting with Möbius Function#

Code#

Complexity#