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

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 <= 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

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

Code

C++

#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;
}

Go

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
}

Java

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;
    }
}

Kotlin

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()]
        }
    }
}

Python

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]

Rust

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()
}

TypeScript

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