GCD Sort of an Array

Problem Description

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.

Key Insights

• The ability to swap elements is determined by their GCD being greater than 1.
• Elements that share a common factor can be considered as part of the same "connected component".
• Sorting is feasible if all elements within the same connected component can be rearranged to match their positions in the sorted version of the array.
• We can use a Union-Find (Disjoint Set Union) data structure to efficiently group elements based on their GCD relationships.

Space and Time Complexity

Time Complexity: O(n log n) for sorting, and O(n α(n)) for union-find operations, where α is the inverse Ackermann function, which is very slow-growing. Thus, it can be considered nearly constant for practical input sizes.

Space Complexity: O(n) for storing the union-find structure and additional data structures.

Solution

The solution involves using a Union-Find (Disjoint Set Union) data structure to group elements that can be swapped based on their GCD. We first connect elements with GCD greater than 1. After forming these groups, we check if we can rearrange the elements within each group to match the sorted version of the original array.

1. Initialize a Union-Find structure.
2. For each pair of elements in the array, if their GCD is greater than 1, union them.
3. For each connected component, gather the elements and their indices.
4. Sort both the gathered elements and the original elements at those indices.
5. If the sorted elements match the original sorted elements, return true; otherwise, return false.

Code Solutions