Sorted GCD Pair Queries - Practice Coding Problems

Sorted GCD Pair Queries - Problem

Array Hash Table Math Binary Search Combinatorics Counting Number Theory Prefix Sum Hard

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,3,4], queries = [0,2,2]

› Output: [1,2,2]

💡 Note: All pairs: (2,3)→gcd=1, (2,4)→gcd=2, (3,4)→gcd=1. Sorted gcdPairs = [1,1,2]. Query results: gcdPairs[0]=1, gcdPairs[2]=2, gcdPairs[2]=2

Example 2 — Duplicates

$ Input: nums = [4,4,2,1], queries = [5,3,1,0]

› Output: [4,2,1,1]

💡 Note: All pairs: (4,4)→gcd=4, (4,2)→gcd=2, (4,1)→gcd=1, (4,2)→gcd=2, (4,1)→gcd=1, (2,1)→gcd=1. Sorted gcdPairs = [1,1,1,2,2,4]. Results: [4,2,1,1]

Example 3 — Small Array

$ Input: nums = [6,9], queries = [0]

› Output: [3]

💡 Note: Only one pair: (6,9)→gcd=3. So gcdPairs = [3] and gcdPairs[0] = 3

Constraints

2 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 5 × 10⁴
1 ≤ queries.length ≤ 10⁵
0 ≤ queries[i] < nums.length × (nums.length - 1) / 2

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums and queries to answer

Generate GCD Pairs

Calculate GCD for all pairs (i,j) where i < j

Sort & Query

Sort GCD values and answer queries by indexing

Key Takeaway

🎯 Key Insight: Transform the problem from pair generation to frequency counting for efficiency

Asked in

G Google 42 M Meta 38 a Amazon 35 m Microsoft 28

The key insight is that instead of generating all O(n²) pairs explicitly, we can use frequency counting and mathematical properties to calculate GCD pair counts efficiently. The brute force approach generates all pairs directly, while the optimized approach uses divisor enumeration and inclusion-exclusion principle. Best approach depends on input size: brute force is simpler for small inputs, optimized is better for large arrays with many duplicates. Time: O(n² log n) brute force vs O(n log n + d² log d) optimized, Space: O(n²) vs O(d)

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Counting with Divisor Enumeration	O(n log n + d² log d)	O(d)	Count frequencies of each number, then enumerate possible GCD values efficiently
Brute Force - Calculate All Pairs	O(n² log n)	O(n²)	Generate all GCD pairs, sort them, then answer queries directly

Frequency Counting with Divisor Enumeration — Algorithm Steps

Count frequency of each number
Find all possible GCD values (divisors)
For each GCD, count pairs using inclusion-exclusion
Build sorted result and answer queries

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count how many times each number appears

Find Divisors

Find all possible GCD values (divisors)

Calculate Pairs

Use inclusion-exclusion to count GCD pairs

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int* solution(int* nums, int numsSize, int* queries, int queriesSize, int* returnSize) {
    // For simplicity, fall back to brute force approach in C
    // A full optimized implementation would require complex hash table management
    
    int pairsCount = (numsSize * (numsSize - 1)) / 2;
    int* gcdPairs = (int*)malloc(pairsCount * sizeof(int));
    int idx = 0;
    
    // Generate all GCD pairs
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            int a = nums[i], b = nums[j];
            // Calculate GCD
            while (b != 0) {
                int temp = b;
                b = a % b;
                a = temp;
            }
            gcdPairs[idx++] = a;
        }
    }
    
    // Sort the GCD pairs
    qsort(gcdPairs, pairsCount, sizeof(int), compare);
    
    // Answer queries
    int* result = (int*)malloc(queriesSize * sizeof(int));
    for (int i = 0; i < queriesSize; i++) {
        result[i] = gcdPairs[queries[i]];
    }
    
    *returnSize = queriesSize;
    free(gcdPairs);
    return result;
}

int main() {
    // Simple demo with hardcoded values
    int nums[] = {2, 3, 4};
    int queries[] = {0, 2, 2};
    int returnSize;
    
    int* result = solution(nums, 3, queries, 3, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + d² log d)

O(n log n) to count frequencies, O(d² log d) where d is number of unique divisors

⚡ Linearithmic

Space Complexity

O(d)

Hash map to store frequency counts and divisor counts

✓ Linear Space

25.0K Views

Medium Frequency

~35 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Counting with Divisor Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler