Package g1901_2000.s1998_gcd_sort_of_an_array

Class Solution

java.lang.Object
g1901_2000.s1998_gcd_sort_of_an_array.Solution
public class Solution extends Object
1998 - GCD Sort of an Array.<p>Hard</p> <p>You are given an integer array <code>nums</code>, and you can perform the following operation <strong>any</strong> number of times on <code>nums</code>:</p> <ul> <li>Swap the positions of two elements <code>nums[i]</code> and <code>nums[j]</code> if <code>gcd(nums[i], nums[j]) > 1</code> where <code>gcd(nums[i], nums[j])</code> is the <strong>greatest common divisor</strong> of <code>nums[i]</code> and <code>nums[j]</code>.</li> </ul> <p>Return <code>true</code> <em>if it is possible to sort</em> <code>nums</code> <em>in <strong>non-decreasing</strong> order using the above swap method, or</em> <code>false</code> <em>otherwise.</em></p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> nums = [7,21,3]</p> <p><strong>Output:</strong> true</p> <p><strong>Explanation:</strong> We can sort [7,21,3] by performing the following operations:</p> <ul> <li> <p>Swap 7 and 21 because gcd(7,21) = 7. nums = [<strong>21</strong> , <strong>7</strong> ,3]</p> </li> <li> <p>Swap 21 and 3 because gcd(21,3) = 3. nums = [<strong>3</strong> ,7, <strong>21</strong> ]</p> </li> </ul> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> nums = [5,2,6,2]</p> <p><strong>Output:</strong> false</p> <p><strong>Explanation:</strong> It is impossible to sort the array because 5 cannot be swapped with any other element.</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> nums = [10,5,9,3,15]</p> <p><strong>Output:</strong> true We can sort [10,5,9,3,15] by performing the following operations:</p> <ul> <li> <p>Swap 10 and 15 because gcd(10,15) = 5. nums = [<strong>15</strong> ,5,9,3, <strong>10</strong> ]</p> </li> <li> <p>Swap 15 and 3 because gcd(15,3) = 3. nums = [<strong>3</strong> ,5,9, <strong>15</strong> ,10]</p> </li> <li> <p>Swap 10 and 15 because gcd(10,15) = 5. nums = [3,5,9, <strong>10</strong> , <strong>15</strong> ]</p> </li> </ul> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= nums.length <= 3 * 10<sup>4</sup></code></li> <li><code>2 <= nums[i] <= 10<sup>5</sup></code></li> </ul>

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • gcdSort

      public boolean gcdSort(int[] nums)