#1998
GCD Sort of an Array
candidate master · 1465 · lc hard +32 · premium · failed · 48.5% accepted · 531 likes · top 34%
Description
Given an integer array nums, you may swap any two elements nums[i] and nums[j] as long as their greatest common divisor gcd(nums[i], nums[j]) > 1. This operation may be repeated any number of times.
Return true if nums can be sorted into non-decreasing order through such swaps, 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]
Code
1
2
3