1998. GCD Sort of an Array Hard

1/**
2 * [1998] GCD Sort of an Array
3 *
4 * You are given an integer array nums, and you can perform the following operation any number of times on nums:
5 * 
6 * 	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].
7 * 
8 * Return true if it is possible to sort nums in non-decreasing order using the above swap method, or false otherwise.
9 *  
10 * Example 1:
11 * 
12 * Input: nums = [7,21,3]
13 * Output: true
14 * Explanation: We can sort [7,21,3] by performing the following operations:
15 * - Swap 7 and 21 because gcd(7,21) = 7. nums = [<u>21</u>,<u>7</u>,3]
16 * - Swap 21 and 3 because gcd(21,3) = 3. nums = [<u>3</u>,7,<u>21</u>]
17 * 
18 * Example 2:
19 * 
20 * Input: nums = [5,2,6,2]
21 * Output: false
22 * Explanation: It is impossible to sort the array because 5 cannot be swapped with any other element.
23 * 
24 * Example 3:
25 * 
26 * Input: nums = [10,5,9,3,15]
27 * Output: true
28 * We can sort [10,5,9,3,15] by performing the following operations:
29 * - Swap 10 and 15 because gcd(10,15) = 5. nums = [<u>15</u>,5,9,3,<u>10</u>]
30 * - Swap 15 and 3 because gcd(15,3) = 3. nums = [<u>3</u>,5,9,<u>15</u>,10]
31 * - Swap 10 and 15 because gcd(10,15) = 5. nums = [3,5,9,<u>10</u>,<u>15</u>]
32 * 
33 *  
34 * Constraints:
35 * 
36 * 	1 <= nums.length <= 3 * 10^4
37 * 	2 <= nums[i] <= 10^5
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/gcd-sort-of-an-array/
43// discuss: https://leetcode.com/problems/gcd-sort-of-an-array/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn gcd_sort(nums: Vec<i32>) -> bool {
49        false
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_1998() {
61    }
62}
63