Sorted GCD Pair Queries

Hard

Asked by:

30 views

Topics:

ArraysTwo PointersGreedy Algorithms

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.

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⁵
1 <= nums[i] <= 5 * 10⁴
1 <= queries.length <= 10⁵
0 <= queries[i] < n * (n - 1) / 2

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the range of numbers in the input array?
Can the input array be empty or contain only one element?
What should I return if no such pair (a, b) exists where GCD(a, b) is sorted?
Is the input array guaranteed to be sorted in ascending order?
If there are multiple pairs with GCDs that are 'sorted', should I return the first one encountered, or is there a specific criterion for selecting one?

Brute Force Solution

Approach

The brute force strategy involves checking every single possible pair of numbers to see if they meet the criteria, and then determining their greatest common divisor. We examine all pairs and compare each result to find the answer to each query.

Here's how the algorithm would work step-by-step:

For each query (asking about a specific range of numbers), consider all possible pairs of numbers within that range.
For each pair, calculate their greatest common divisor, which is the largest number that divides both numbers without any remainder.
Keep track of all the greatest common divisors you've calculated for the given range of numbers.
Sort all the calculated greatest common divisors from smallest to largest.
Return these sorted values as the answer.

Code Implementation

def sorted_gcd_pair_queries_brute_force(numbers, query_start, query_end):    gcd_values = []
    # Iterate through each possible pair of numbers in the range.
    for first_index in range(query_start, query_end + 1):
        for second_index in range(first_index + 1, query_end + 1):
            # Calculate the GCD for the current pair.
            current_gcd = calculate_gcd(numbers[first_index], numbers[second_index])
            gcd_values.append(current_gcd)

    # Sorting is necessary to fulfill problem requirements.
    gcd_values.sort()
    return gcd_values

def calculate_gcd(first_number, second_number):
    while(second_number):
        first_number, second_number = second_number, first_number % second_number
    return first_number

Big(O) Analysis

Time Complexity

O(n^2 log n) – For each query with a range of size n, the brute force approach considers all possible pairs, which takes O(n^2) time. For each pair, computing the greatest common divisor (GCD) typically takes O(log m) time where m is the maximum value in the input array. However, since 'm' is bounded in this case, we can treat GCD calculation as constant time for simplicity, but we must still account for sorting. After calculating the GCD for all pairs, we sort the GCDs, which takes O(n^2 log (n^2)) which simplifies to O(n^2 log n) time. The sorting operation dominates the complexity of calculating the GCD for each pair. Thus the overall time complexity for each query is O(n^2 log n).

Space Complexity

O(N^2) – The algorithm stores calculated greatest common divisors in a collection to enable sorting. In the worst-case scenario, where all GCDs within the range are distinct, this collection could grow to a size proportional to the number of possible pairs. Since the number of possible pairs within a range of size N is N*(N-1)/2, the space required to store these GCDs will be proportional to N^2. Therefore, the auxiliary space complexity is O(N^2).

Optimal Solution

Approach

The fastest way to answer these questions is to process all the numbers first so we can quickly give answers later. We'll precompute and store all the possible GCD values so we can avoid recalculating them for each query.

Here's how the algorithm would work step-by-step:

First, we figure out all the unique numbers that appear in the original list of numbers. This is because the greatest common divisor (GCD) of any pair of numbers can only be one of these unique numbers.
Next, we'll count how many times each of these unique numbers appears in the sorted list. We will leverage the fact the list is already sorted.
Then, for each query asking about a specific GCD, we'll quickly find the number of pairs with that GCD using the stored counts.
To find the number of pairs, we multiply the count of each unique number by the sum of the counts of all numbers that are multiples of that number, making sure not to double-count the case where the two numbers are equal.
Finally, we will return the number of sorted pairs we found.

Code Implementation

def sorted_gcd_pair_queries(numbers, queries):
    unique_numbers = sorted(list(set(numbers)))

    counts = {}
    for number in unique_numbers:
        counts[number] = 0
    
    for number in numbers:
        if number in counts:
            counts[number] += 1

    results = []
    for gcd_value in queries:
        pair_count = 0

        # Iterate through each unique number to find GCD pairs
        for first_number in unique_numbers:
            if first_number < gcd_value:
                continue
            
            multiple_count = 0
            for second_number in unique_numbers:
                if second_number >= gcd_value and second_number % gcd_value == 0 and first_number % second_number == 0:

                    # Summing counts of all multiples of gcd
                    multiple_count += counts[second_number]
            if first_number % gcd_value == 0:
                pair_count += counts[first_number] * multiple_count

        results.append(pair_count)

    return results

Big(O) Analysis

Time Complexity

O(m * log(MAX) + q) – Let n be the size of the input array and m be the number of unique elements after sorting. MAX is the maximum value in the input array. Identifying unique elements and counting their occurrences takes O(m) time since the input is sorted. Computing multiples involves at most log(MAX) iterations for each of the m unique numbers (since we consider multiples up to MAX). Thus, finding and counting pairs takes O(m * log(MAX)) time. Finally, answering q queries takes O(q) time, assuming the precomputed counts are stored in a hashmap for O(1) lookup per query. Thus the total time complexity is O(m * log(MAX) + q).

Space Complexity

O(U) – The auxiliary space is dominated by the storage of unique numbers and their counts. We store all unique numbers from the input list of size N, resulting in at most U unique numbers, where U <= N. We also store the counts of these unique numbers, using another data structure of size U. Therefore, the space complexity is proportional to the number of unique elements U, giving a space complexity of O(U).

Edge Cases

Case	How to Handle
Empty input array	Return an empty list since no GCD pairs can be formed.
Array with a single element	Return an empty list as a pair requires at least two elements.
All elements in the array are the same	Calculate the GCD of the first two elements which are identical; then find all pairs with that GCD.
Array contains zero	GCD(0, x) = x; handle zero values during GCD calculation, e.g., skip them or define GCD(0,0) = 0.
Large input array size	Optimize the GCD calculation using efficient algorithms and data structures to avoid exceeding time limits.
Large integer values in the input array causing integer overflow	Use a data type that can accommodate larger numbers (e.g., long) or use modular arithmetic if applicable to prevent integer overflow.
Target GCD query not present in any pair	Return an empty list since no such pair exists.
Negative integers present in the array	Take the absolute value of numbers before calculating the GCD since GCD is always non-negative, or handle this specifically according to problem requirements if negatives are involved.

Empty input array

How to Handle:

Return an empty list since no GCD pairs can be formed.

Array with a single element

How to Handle:

Return an empty list as a pair requires at least two elements.

All elements in the array are the same

How to Handle:

Calculate the GCD of the first two elements which are identical; then find all pairs with that GCD.

Array contains zero

How to Handle:

GCD(0, x) = x; handle zero values during GCD calculation, e.g., skip them or define GCD(0,0) = 0.

Large input array size

How to Handle:

Optimize the GCD calculation using efficient algorithms and data structures to avoid exceeding time limits.

Large integer values in the input array causing integer overflow

How to Handle:

Use a data type that can accommodate larger numbers (e.g., long) or use modular arithmetic if applicable to prevent integer overflow.

Target GCD query not present in any pair

How to Handle:

Return an empty list since no such pair exists.

Negative integers present in the array

How to Handle:

Take the absolute value of numbers before calculating the GCD since GCD is always non-negative, or handle this specifically according to problem requirements if negatives are involved.