GCD Sort of an Array

Hard

Asked by:

12 views

Topics:

ArraysGreedy Algorithms

You are given an integer array nums, and you can perform the following operation any number of times on nums:

Swap the positions of two elements nums[i] and nums[j] if gcd(nums[i], nums[j]) > 1 where gcd(nums[i], nums[j]) is the greatest common divisor of nums[i] and nums[j].

Return true if it is possible to sort nums in non-decreasing order using the above swap method, or false otherwise.

Example 1:

Input: nums = [7,21,3]
Output: true
Explanation: We can sort [7,21,3] by performing the following operations:
- Swap 7 and 21 because gcd(7,21) = 7. nums = [21,7,3]
- Swap 21 and 3 because gcd(21,3) = 3. nums = [3,7,21]

Example 2:

Input: nums = [5,2,6,2]
Output: false
Explanation: It is impossible to sort the array because 5 cannot be swapped with any other element.

Example 3:

Input: nums = [10,5,9,3,15]
Output: true
We can sort [10,5,9,3,15] by performing the following operations:
- Swap 10 and 15 because gcd(10,15) = 5. nums = [15,5,9,3,10]
- Swap 15 and 3 because gcd(15,3) = 3. nums = [3,5,9,15,10]
- Swap 10 and 15 because gcd(10,15) = 5. nums = [3,5,9,10,15]

Constraints:

1 <= nums.length <= 3 * 10⁴
2 <= nums[i] <= 10⁵

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 is the range of values for the integers in the input array? Could they be negative or zero?
What should I return if the array is already GCD sorted? Should I return true, or perform the sort operation regardless?
Can the input array contain duplicate numbers, and if so, how should they be handled during the GCD check and sorting process?
Is there a specific error condition I should be checking for, such as an empty input array, and what should I return in such a case?
Are we looking for a specific sorting algorithm to be used, or can I choose the most efficient one that satisfies the GCD sort criteria?

Brute Force Solution

Approach

The brute force approach to GCD sorting is all about trying every possible arrangement of the numbers. We'll check if each arrangement meets the GCD criteria after we sort it.

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

First, let's consider every single possible order of the numbers you've been given. Imagine writing them all down separately on different pieces of paper.
For each of those orders, we would sort the numbers and then we'll check if that sorted arrangement meets the 'GCD' criteria with adjacent numbers.
Checking 'GCD' criteria involves figuring out the greatest common divisor between all the neighboring pairs of numbers, in the sorted arrangement, and checking if the original unsorted number had the same GCD.
If we encounter an arrangement of numbers that meets the GCD criteria, that means a solution has been found. We can stop searching at that point.
If we check every single arrangement and don't find one that works, then it's impossible to arrange the numbers in a way that satisfies GCD criteria with adjacent numbers.

Code Implementation

def gcd_sort_brute_force(numbers):    import itertools
    def greatest_common_divisor(first_number, second_number):
        while(second_number):
            first_number, second_number = second_number, first_number % second_number
        return first_number
    def check_gcd_criteria(original_numbers, sorted_numbers):
        for index in range(len(sorted_numbers) - 1):
            if greatest_common_divisor(sorted_numbers[index], sorted_numbers[index + 1]) != greatest_common_divisor(original_numbers[index], original_numbers[index + 1]):
                return False
        return True
    # Generate all possible permutations of the input array
    for permutation in itertools.permutations(numbers):
        permutation_list = list(permutation)
        sorted_permutation = sorted(permutation_list)

        # Check if the current permutation meets the GCD criteria
        if len(numbers) > 1:
            if check_gcd_criteria(numbers, sorted_permutation):
                return True
        else:
            return True
    # If no permutation satisfies the condition, return False
    return False

Big(O) Analysis

Time Complexity

O(n! * n log n) – The brute force approach considers all possible permutations of the input array, which has n! possible arrangements. For each permutation, the array is sorted, which takes O(n log n) time. The GCD criteria check within each permutation would take O(n) time, but it is dominated by the sorting time, so we can ignore it. Therefore, the total time complexity is O(n! * n log n).

Space Complexity

O(N!) – The described brute force approach generates every possible permutation of the input array, requiring storing each permutation before checking the GCD criteria. Generating all permutations of an array of size N requires space to hold each permutation. In the worst case, we may need to store all N! permutations before finding a solution or determining that none exists, leading to O(N!) auxiliary space.

Optimal Solution

Approach

We want to check if we can sort the numbers by only swapping numbers that share a common factor (greater than 1). Instead of directly sorting, we'll build a connection map showing which numbers *could* be swapped and then check if we could indirectly sort the array.

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

Figure out the biggest number in the initial list.
Create a new list of all the numbers from one up to that biggest number.
For each number in the original list figure out its common factors.
Also for each number in the sorted list, find it's common factors.
Now, connect numbers that share common factors. Think of this as creating a map of swappable positions.
Check if the numbers in the original list are connected to the numbers that they would need to be swapped with in the sorted version.
If all the needed numbers in the original list are connected to their counterparts in the sorted list then it is possible, otherwise it's not.

Code Implementation

def gcd_sort(numbers):
    array_length = len(numbers)
    max_number = max(numbers)
    
    parent = list(range(max_number + 1))
    
    def find(number):
        if parent[number] != number:
            parent[number] = find(parent[number])
        return parent[number]
    
    def union(number_x, number_y):
        root_x = find(number_x)
        root_y = find(number_y)
        if root_x != root_y:
            parent[root_x] = root_y

    # Iterate from 2 to the max to find factors.
    for factor in range(2, max_number + 1):
        for number in range(factor, max_number + 1, factor):
            # Connect all numbers divisible by the same factor.
            union(factor, number)

    sorted_numbers = sorted(numbers)

    # Checking connectivity between unsorted and sorted positions.
    for index in range(array_length):
        if find(numbers[index]) != find(sorted_numbers[index]):
            return False

    return True

Big(O) Analysis

Time Complexity

O(maxVal * log(maxVal) + n * alpha(n)) – Finding the largest number in the initial list takes O(n). Creating a list of numbers up to the maximum value (maxVal) takes O(maxVal). Finding common factors for each number up to maxVal can take O(sqrt(maxVal)), and with maxVal numbers it becomes O(maxVal * sqrt(maxVal)). However, using a sieve-like approach to precompute the smallest prime factor for each number up to maxVal allows finding factors in O(log(maxVal)), resulting in O(maxVal * log(maxVal)) for factor computation. Connecting numbers and checking connectivity using a Union-Find data structure takes O(n * alpha(n)), where alpha(n) is the inverse Ackermann function, which grows very slowly and can be considered almost constant for practical input sizes. Thus the dominant terms are O(maxVal * log(maxVal) + n * alpha(n)).

Space Complexity

O(max(N, M)) – The algorithm creates a new list of numbers from 1 up to the biggest number in the initial list, contributing O(M) space, where M is the maximum value in the input array. A connection map or Union-Find data structure is implicitly used to track swappable positions, which in the worst case could require space proportional to the number of elements, contributing O(N) where N is the length of original array. Therefore, the space complexity is determined by the larger of these two factors.

Edge Cases

Case	How to Handle
Empty or null input array	Return true, as an empty array is trivially considered sorted in this context because no swap needs to be made.
Array with only one element	Return true, as a single-element array is also trivially considered sorted because there's nothing to sort.
Array with all identical values	The algorithm should correctly identify this as already sorted (or sortable without actual swaps), returning true.
Large input array (maximum-sized)	Ensure the used sorting and GCD algorithms scale efficiently to avoid time limit exceeded errors; consider using an optimized sorting algorithm and a fast GCD implementation (e.g., binary GCD).
Integer overflow during GCD calculation	Use a data type large enough to prevent overflow (e.g., long in Java/C++) when calculating GCDs, or bitwise operations to avoid multiplication.
Input array contains zero	The GCD function must handle zero inputs gracefully, typically returning the non-zero number or zero if both inputs are zero.
Input array contains large prime numbers	GCD calculation involving large primes may be computationally expensive, but the algorithm should still function correctly, although possibly slower.
No valid solution exists (array is not GCD sortable)	The algorithm must correctly identify when the array cannot be sorted by GCD swaps and return false, which will be indicated when there is an element out of order and no element earlier in the array has a gcd with it.

Empty or null input array

How to Handle:

Return true, as an empty array is trivially considered sorted in this context because no swap needs to be made.

Array with only one element

How to Handle:

Return true, as a single-element array is also trivially considered sorted because there's nothing to sort.

Array with all identical values

How to Handle:

The algorithm should correctly identify this as already sorted (or sortable without actual swaps), returning true.

Large input array (maximum-sized)

How to Handle:

Ensure the used sorting and GCD algorithms scale efficiently to avoid time limit exceeded errors; consider using an optimized sorting algorithm and a fast GCD implementation (e.g., binary GCD).

Integer overflow during GCD calculation

How to Handle:

Use a data type large enough to prevent overflow (e.g., long in Java/C++) when calculating GCDs, or bitwise operations to avoid multiplication.

Input array contains zero

How to Handle:

The GCD function must handle zero inputs gracefully, typically returning the non-zero number or zero if both inputs are zero.

Input array contains large prime numbers

How to Handle:

GCD calculation involving large primes may be computationally expensive, but the algorithm should still function correctly, although possibly slower.

No valid solution exists (array is not GCD sortable)

How to Handle:

The algorithm must correctly identify when the array cannot be sorted by GCD swaps and return false, which will be indicated when there is an element out of order and no element earlier in the array has a gcd with it.