3312. Sorted GCD Pair Queries

HardArrayHash TableMathBinary SearchCombinatoricsCountingNumber TheoryPrefix Sum

Problem Description

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

Let gcdPairs denote an array obtained by calculating the Greatest Common Divisor (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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve the problem efficiently, we use a preprocessing approach combined with the concept of prefix sums and binary search.

Count Occurrences: Record the occurrence count of each number in the nums array using a counter. This helps us identify how often each number appears, which is essential for counting pairs with specific GCDs.
Determine GCD Pairs Count (cntG): For each possible GCD i from the maximum value in nums down to 1, calculate how many pairs in nums have a GCD equal to i. This involves:
- Counting how many multiples of i exist in nums.
- Calculating the number of pairs that can be formed from these multiples, which gives potential GCDs that are multiples of i.
Exclude Higher Multiples: To ensure that only pairs with exactly GCD i are counted, subtract cases where the GCD is a larger multiple of i.
Prefix Sum Calculation: Compute a prefix sum array of the cntG values. This helps answer the queries efficiently by summing up the number of GCD pairs efficiently.
Binary Search for Queries: For each query, use binary search on the prefix sum array to determine the index of the GCD pair that matches the given query. This allows finding the answer for each query in logarithmic time.

These steps enable efficient calculation and retrieval of GCD pairs, allowing the answer to be constructed swiftly for each query provided.

Learn more about Math, Binary Search, Combinatorics and Prefix Sum patterns.

Solution Approach

To implement the solution, we employ a combination of preprocessing, prefix sums, and binary search. Here is the step-by-step approach:

Identify Maximum Value: Find the maximum value in the nums array, denoted as mx. This helps set the range for potential GCD calculations.
Count Elements: Create a counter cnt to record the occurrence of each number in nums. This is crucial for determining how many pairs can be formed from any selected number.
Compute GCD Pair Counts (cntG):
- Initialize an array cnt_g of size mx + 1 to zero. This will store the number of pairs that have a GCD equal to each index.
- Iterate from i = mx down to 1:
  - Calculate v, the number of multiples of i within nums. For each multiplier j of i, sum the occurrences from cnt[j].
  - Increase cnt_g[i] by the count of pairs that can be formed from these multiples, v * (v - 1) // 2.
  - Subtract from cnt_g[i] any previously calculated cnt_g[j] for multiples j of i that are greater than i to adjust for overcounting.
Compute Prefix Sums: Use the accumulate function to generate a prefix sum array s from cnt_g. Prefix sums allow quick range sum queries necessary for finding the target GCD value in response to queries.
Answer Queries Using Binary Search:
- For each query in queries, use bisect_right on the prefix sum array s to efficiently find the smallest index where the cumulative sum exceeds the query value. This index indicates the position in gcdPairs corresponding to the query.

These steps are implemented in a concise manner utilizing Python's Counter, accumulate, and bisect_right functions to efficiently manage counts, accumulate results, and perform binary searching, respectively.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the integer array nums = [2, 3, 4] and the query array queries = [0, 2].

1. Identify the Maximum Value:

The maximum value in nums is 4.

2. Count Elements:

Using a counter, count occurrences in nums:
- cnt = {2: 1, 3: 1, 4: 1}

3. Compute GCD Pair Counts (cntG):

Initialize cnt_g = [0, 0, 0, 0, 0] for indices 0 to 4.
For i=4:
- v (number of multiples) is 1 (only 4 itself). Since v < 2, pairs are not possible.
For i=3:
- v is 1 (only 3). No pairs possible.
For i=2:
- v is 2 (multiples are 2 and 4).
- Possible pairs: 1 (2, 4), so cnt_g[2] = 1.
For i=1:
- v is 3 (all numbers can be paired).
- Possible pairs: 3 (2, 3, 2, 4, 3, 4).
- Subtract: Any larger cnt_g[j] for j > 1, thus cnt_g[1] = 3 - 1 = 2.

Resulting cnt_g:

cnt_g = [0, 2, 1, 0, 0]

4. Compute Prefix Sums:

Compute prefix sum s as:
- s = [0, 2, 3, 3, 3]

5. Answer Queries Using Binary Search:

For queries[0] = 0:
- Find index via bisect_right(s, 0), results in 1. GCD is 1.
For queries[2] = 2:
- Find index via bisect_right(s, 2), results in 2. GCD is 2.

Final Answer:

The answer array is [1, 2], representing the GCD values at the gcdPairs indices specified by queries.

Solution Implementation

1from typing import List
2from collections import Counter
3from itertools import accumulate
4from bisect import bisect_right
5
6class Solution:
7    def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:
8        # Find the maximum value in nums to define the range for gcd calculations
9        max_num = max(nums)
10      
11        # Count the frequency of each number in nums
12        num_count = Counter(nums)
13      
14        # Create a list to hold the gcd pair count for each possible gcd value
15        gcd_count = [0] * (max_num + 1)
16      
17        # Traverse all numbers from max_num down to 1
18        for i in range(max_num, 0, -1):
19            num_pairs = 0
20          
21            # Aggregate counts of numbers that are multiples of i
22            for j in range(i, max_num + 1, i):
23                num_pairs += num_count[j]
24                gcd_count[i] -= gcd_count[j]
25          
26            # Calculate combinations of pairs for each gcd value
27            gcd_count[i] += num_pairs * (num_pairs - 1) // 2
28      
29        # Accumulate the counts to efficiently find the result for each query
30        accumulated_counts = list(accumulate(gcd_count))
31      
32        # Use binary search to find the smallest index where accumulated count exceeds each query
33        return [bisect_right(accumulated_counts, query) for query in queries]
34

1import java.util.Arrays;
2
3class Solution {
4    public int[] gcdValues(int[] nums, long[] queries) {
5        // Find the maximum value in the nums array
6        int maxVal = Arrays.stream(nums).max().getAsInt();
7
8        // Array to count occurrences of each number up to maxVal
9        int[] count = new int[maxVal + 1];
10
11        // Array to store the number of gcd pairs for each gcd value
12        long[] gcdPairCount = new long[maxVal + 1];
13
14        // Count occurrences of each number in nums
15        for (int num : nums) {
16            count[num]++;
17        }
18
19        // Calculate gcd pairs for each possible gcd using a backwards loop
20        for (int i = maxVal; i > 0; --i) {
21            int pairCount = 0;
22            for (int j = i; j <= maxVal; j += i) {
23                pairCount += count[j];
24                gcdPairCount[i] -= gcdPairCount[j];
25            }
26            gcdPairCount[i] += 1L * pairCount * (pairCount - 1) / 2;
27        }
28
29        // Accumulate counts to make use of prefix sums
30        for (int i = 2; i <= maxVal; ++i) {
31            gcdPairCount[i] += gcdPairCount[i - 1];
32        }
33
34        int queryCount = queries.length;
35        int[] answers = new int[queryCount];
36
37        // Answer each query by finding the largest gcd with sufficient pairs
38        for (int i = 0; i < queryCount; ++i) {
39            answers[i] = search(gcdPairCount, queries[i]);
40        }
41
42        return answers;
43    }
44
45    // Binary search to find the smallest index with a value greater than x
46    private int search(long[] nums, long x) {
47        int length = nums.length;
48        int left = 0, right = length;
49      
50        while (left < right) {
51            int mid = (left + right) >> 1;
52            if (nums[mid] > x) {
53                right = mid;  // Search in the left half
54            } else {
55                left = mid + 1;  // Search in the right half
56            }
57        }
58      
59        return left;
60    }
61}
62

1#include <vector>
2#include <algorithm> // For std::upper_bound
3using namespace std;
4
5class Solution {
6public:
7    vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {
8        int maxValue = *max_element(nums.begin(), nums.end());
9
10        // Count occurrences of each number in nums
11        vector<int> count(maxValue + 1);
12        for (int x : nums) {
13            ++count[x];
14        }
15
16        // Array to keep track of cumulative gcd count values
17        vector<long long> gcdCount(maxValue + 1);
18
19        // Calculate the number of pairs having gcd equal to i
20        for (int i = maxValue; i > 0; --i) {
21            long long pairCount = 0;
22            for (int j = i; j <= maxValue; j += i) {
23                // Sum up counts of multiples of i
24                pairCount += count[j];
25                // Subtract the gcdCount of higher multiples
26                gcdCount[i] -= gcdCount[j];
27            }
28            // Calculate pair combinations using nC2 = n * (n - 1) / 2
29            gcdCount[i] += 1LL * pairCount * (pairCount - 1) / 2;
30        }
31
32        // Accumulate counts to get the total number of valid gcd pairs for each gcd value
33        for (int i = 2; i <= maxValue; ++i) {
34            gcdCount[i] += gcdCount[i - 1];
35        }
36
37        // Result vector to store the answers for each query
38        vector<int> result;
39        for (auto q : queries) {
40            // Find the smallest i such that gcdCount[i] > queries[q] using upper_bound
41            result.push_back(upper_bound(gcdCount.begin(), gcdCount.end(), q) - gcdCount.begin());
42        }
43
44        return result;
45    }
46};
47

1// Helper function to find the maximum element in an array
2const maxElement = (nums: number[]): number => {
3    return Math.max(...nums); 
4};
5
6// Function to calculate the greatest common divisor (gcd) values
7function gcdValues(nums: number[], queries: number[]): number[] {
8    const maxValue = maxElement(nums);
9
10    // Initialize count array to count occurrences of each number in nums
11    const count: number[] = new Array(maxValue + 1).fill(0);
12    for (const x of nums) {
13        count[x]++;
14    }
15
16    // Array to keep track of cumulative gcd count values
17    const gcdCount: number[] = new Array(maxValue + 1).fill(0);
18
19    // Calculate the number of pairs having gcd equal to i
20    for (let i = maxValue; i > 0; i--) {
21        let pairCount = 0;
22        for (let j = i; j <= maxValue; j += i) {
23            // Sum up counts of multiples of i
24            pairCount += count[j];
25            // Subtract the gcdCount of higher multiples
26            gcdCount[i] -= gcdCount[j];
27        }
28        // Calculate pair combinations using nC2 = n * (n - 1) / 2
29        gcdCount[i] += Math.floor(1 * pairCount * (pairCount - 1) / 2);
30    }
31
32    // Accumulate counts to get the total number of valid gcd pairs for each gcd value
33    for (let i = 2; i <= maxValue; i++) {
34        gcdCount[i] += gcdCount[i - 1];
35    }
36
37    // Result array to store the answers for each query
38    const result: number[] = [];
39    for (const q of queries) {
40        // Find the smallest i such that gcdCount[i] > q using upper_bound equivalent
41        // using Array.prototype.findIndex
42        const upperBoundIndex = gcdCount.findIndex(val => val > q);
43        result.push(upperBoundIndex !== -1 ? upperBoundIndex : maxValue + 1);
44    }
45
46    return result;
47}
48

Time and Space Complexity

The time complexity of the given code is O(n + (M + q) \times \log M), where n is the length of nums, M is the maximum value in nums, and q is the number of elements in queries. This complexity arises because the algorithm processes the counter for each number up to M and performs binary searches for each query.

The space complexity is O(M), due to the storage required for cnt, cnt_g, and the accumulator list s. These arrays are sized based on the maximum value M.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan: