You are given an integer array nums, and you can perform the following operation any number of times on nums:
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 * 1042 <= nums[i] <= 105#1998 GCD Sort of an Array asks whether an array can be sorted if you are only allowed to swap two elements whose gcd(a, b) > 1. The key insight is that elements can be swapped indirectly through chains of numbers sharing common prime factors.
An efficient strategy uses Union-Find (Disjoint Set Union) combined with number theory. First, compute prime factors for each number (often using a smallest-prime-factor sieve). Then union each number with its prime factors so that numbers sharing a common factor belong to the same connected component. After building these components, compare the original array with its sorted version. If every element can move to its sorted position within the same connected component, sorting is possible.
This approach avoids brute-force swaps and leverages factor connectivity. With sieve-based factorization and DSU operations, the overall complexity is roughly O(n log M) or O(n α(n)) for union operations, where M is the maximum value in the array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Union-Find with Prime Factorization | O(n log M) | O(M) |
| Union-Find Operations | O(n α(n)) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Can we build a graph with all the prime numbers and the original array?
We can use union-find to determine which indices are connected (i.e., which indices can be swapped).
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems combining Union-Find and number theory are common in top tech interviews. This problem tests knowledge of disjoint sets, prime factorization, and optimization techniques used in large-scale algorithmic challenges.
The optimal approach uses Union-Find combined with prime factorization. By connecting numbers that share common prime factors, we form components where swaps are allowed. If each element can move to its sorted position within the same component, the array can be sorted.
Number theory helps identify prime factors of each number. If two numbers share a common factor greater than 1, they can be connected in the same component, enabling indirect swaps through factor-based connectivity.
The Disjoint Set Union (Union-Find) data structure is the most suitable. It efficiently groups numbers that share common factors and allows quick checks to determine whether two indices belong to the same swappable component.