1998. GCD Sort of an Array

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.

 

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 * 104
• 2 <= nums[i] <= 105

 

Solutions

Solution: Union Find + Sieve of Eratosthenes

• Time complexity: O(nlogn+nlogMax(nums)+Max(nums)log(logMax(nums)))
• Space complexity: O(n+Max(nums))

 

JavaScript

/**
 * @param {number[]} nums
 * @return {boolean}
 */
const gcdSort = function (nums) {
  const maxNum = Math.max(...nums);
  const sortedNums = [...nums].sort((a, b) => a - b);
  const uf = new UnionFind(maxNum + 1);
  const minPrimeSieve = Array.from({ length: maxNum + 1 }, (_, index) => index);

  minPrimeSieve[0] = 0;
  minPrimeSieve[1] = 0;

  const getPrimeFactors = num => {
    const result = [];

    while (num > 1) {
      const prime = minPrimeSieve[num];

      result.push(prime);

      while (num % prime === 0) {
        num /= prime;
      }
    }

    return result;
  };

  for (let num = 2; num * num <= maxNum; num++) {
    if (minPrimeSieve[num] !== num) continue;

    for (let factor = num * num; factor <= maxNum; factor += num) {
      minPrimeSieve[factor] = num;
    }
  }

  for (const num of nums) {
    const primeFactors = getPrimeFactors(num);

    for (const factor of primeFactors) {
      uf.union(num, factor);
    }
  }

  return nums.every((num, index) => uf.find(num) === uf.find(sortedNums[index]));
};

class UnionFind {
  constructor(n) {
    this.groups = Array.from({ length: n }, (_, index) => index);
    this.ranks = Array.from({ length: n }, () => 0);
  }

  find(node) {
    if (this.groups[node] === node) return node;
    const group = this.find(this.groups[node]);

    this.groups[node] = group;
    return group;
  }

  union(a, b) {
    const groupA = this.find(a);
    const groupB = this.find(b);

    if (groupA === groupB) return false;
    if (this.ranks[groupA] > this.ranks[groupB]) {
      this.groups[groupB] = groupA;
    } else if (this.ranks[groupA] < this.ranks[groupB]) {
      this.groups[groupA] = groupB;
    } else {
      this.groups[groupB] = groupA;
      this.ranks[groupA] += 1;
    }

    return true;
  }
}