{x}
blog image

GCD Sort of an Array

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

Problem Description

The problem asks whether it's possible to sort an array nums in non-decreasing order by repeatedly swapping pairs of elements nums[i] and nums[j] if their greatest common divisor (GCD) is greater than 1.

Solution Explanation

The solution uses Union-Find to efficiently determine if sorting is possible. The core idea is that if two numbers share a GCD greater than 1, they belong to the same connected component in a graph where nodes are numbers and edges exist between numbers with a GCD > 1. If the sorted array has numbers from different connected components in the same positions as the original array, then it's impossible to sort the array using the allowed swaps.

Here's a breakdown of the steps:

  1. Preprocessing:

    • Create a Union-Find data structure (p array). Initially, each number is in its own set.
    • Create a map f to store prime factors for each number up to the maximum value in nums. This helps efficiently find numbers that share GCDs greater than 1. For each number, its prime factors are added to the f map.

  2. Union-Find Operations:

    • Iterate through each number i in nums.
    • For each prime factor j of i, union the set containing i with the set containing j using the find and union functions of the Union-Find data structure. This ensures numbers sharing a common factor are in the same set.

  3. Checking Sortability:

    • Create a sorted copy s of nums.
    • Iterate through nums and s simultaneously.
    • If nums[i] and s[i] are different and belong to different sets (i.e., find(nums[i]) != find(s[i])), it's impossible to sort nums, so return false.

  4. Return True:

    • If the loop completes without finding any such conflicting pairs, return true.

Time Complexity Analysis

  • Preprocessing (finding prime factors): The complexity of finding prime factors for all numbers up to mx (maximum value in nums) is dominated by the sieve method, which is O(mx log log mx).
  • Union-Find operations: Each number is processed once, and the union operation takes amortized O(α(n)) time, where α is the inverse Ackermann function and n is the number of elements. Since α(n) is nearly constant for practical purposes, the overall complexity is O(n), where n is the length of nums.
  • Checking sortability: This step iterates through the array once, so its complexity is O(n).

Therefore, the overall time complexity is dominated by the preprocessing step, making it approximately O(mx log log mx), where mx is the maximum value in nums. In the worst case, mx could be very close to 10^5, but in many practical cases, this might be much smaller. The space complexity is also O(mx) to store the f map and Union-Find set.

Space Complexity Analysis

The space complexity is O(mx), where mx is the maximum value in nums, because of the prime factor map f and the Union-Find data structure p. The sorted array s uses O(n) space, but this is dominated by the O(mx) space.