Problem

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 sortnums _innon-decreasing order using the above swap method, or _false otherwise.

Examples

Example 1

1
2
3
4
5

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

1
2
3

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

1
2
3
4
5
6

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 * 10^4
  • 2 <= nums[i] <= 10^5

Solution

Method 1 – Union-Find with Prime Factor Connectivity

Intuition

We can only swap two numbers if they share a common prime factor (gcd > 1). If we connect all numbers that share a prime factor using union-find, then for each connected component, we can sort the numbers within that component. If the sorted array can be formed by rearranging numbers within their components, the answer is true.

Approach

  1. For each number, factorize it and union the number with all its prime factors.
  2. For each number, union all its prime factors using a union-find data structure.
  3. For each connected component, collect all indices and values, and check if the sorted values can be placed at those indices in the sorted array.
  4. If all numbers can be rearranged within their components to match the sorted array, return true; otherwise, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    int find(vector<int>& p, int x) {
        if (p[x] != x) p[x] = find(p, p[x]);
        return p[x];
    }
    bool gcdSort(vector<int>& nums) {
        int mx = *max_element(nums.begin(), nums.end());
        vector<int> p(mx + 1);
        iota(p.begin(), p.end(), 0);
        for (int x : nums) {
            int y = x;
            for (int d = 2; d * d <= y; ++d) {
                if (y % d == 0) {
                    p[find(p, x)] = find(p, d);
                    while (y % d == 0) y /= d;
                }
            }
            if (y > 1) p[find(p, x)] = find(p, y);
        }
        vector<int> sorted = nums;
        sort(sorted.begin(), sorted.end());
        for (int i = 0; i < nums.size(); ++i) {
            if (find(p, nums[i]) != find(p, sorted[i])) return false;
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

type Solution struct{}
func (Solution) gcdSort(nums []int) bool {
    mx := 0
    for _, x := range nums {
        if x > mx { mx = x }
    }
    p := make([]int, mx+1)
    for i := range p { p[i] = i }
    find := func(x int) int {
        for p[x] != x { p[x] = p[p[x]]; x = p[x] }
        return x
    }
    for _, x := range nums {
        y := x
        for d := 2; d*d <= y; d++ {
            if y%d == 0 {
                px, pd := find(x), find(d)
                p[px] = pd
                for y%d == 0 { y /= d }
            }
        }
        if y > 1 { p[find(x)] = find(y) }
    }
    sorted := append([]int(nil), nums...)
    sort.Ints(sorted)
    for i, v := range nums {
        if find(v) != find(sorted[i]) { return false }
    }
    return true
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public boolean gcdSort(int[] nums) {
        int mx = 0;
        for (int x : nums) mx = Math.max(mx, x);
        int[] p = new int[mx + 1];
        for (int i = 0; i <= mx; i++) p[i] = i;
        java.util.function.IntUnaryOperator find = new java.util.function.IntUnaryOperator() {
            public int applyAsInt(int x) {
                if (p[x] != x) p[x] = applyAsInt(p[x]);
                return p[x];
            }
        };
        for (int x : nums) {
            int y = x;
            for (int d = 2; d * d <= y; d++) {
                if (y % d == 0) {
                    p[find.applyAsInt(x)] = find.applyAsInt(d);
                    while (y % d == 0) y /= d;
                }
            }
            if (y > 1) p[find.applyAsInt(x)] = find.applyAsInt(y);
        }
        int[] sorted = nums.clone();
        java.util.Arrays.sort(sorted);
        for (int i = 0; i < nums.length; i++) {
            if (find.applyAsInt(nums[i]) != find.applyAsInt(sorted[i])) return false;
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    fun gcdSort(nums: IntArray): Boolean {
        val mx = nums.maxOrNull() ?: 0
        val p = IntArray(mx + 1) { it }
        fun find(x: Int): Int {
            if (p[x] != x) p[x] = find(p[x])
            return p[x]
        }
        for (x in nums) {
            var y = x
            var d = 2
            while (d * d <= y) {
                if (y % d == 0) {
                    p[find(x)] = find(d)
                    while (y % d == 0) y /= d
                }
                d++
            }
            if (y > 1) p[find(x)] = find(y)
        }
        val sorted = nums.sorted()
        for (i in nums.indices) {
            if (find(nums[i]) != find(sorted[i])) return false
        }
        return true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def gcdSort(self, nums: list[int]) -> bool:
        from math import gcd
        n = max(nums)
        p = list(range(n + 1))
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]
        def union(x, y):
            p[find(x)] = find(y)
        def factorize(x):
            d = 2
            res = set()
            while d * d <= x:
                if x % d == 0:
                    res.add(d)
                    while x % d == 0:
                        x //= d
                d += 1
            if x > 1:
                res.add(x)
            return res
        for x in nums:
            for f in factorize(x):
                union(x, f)
        sorted_nums = sorted(nums)
        for a, b in zip(nums, sorted_nums):
            if find(a) != find(b):
                return False
        return True
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

impl Solution {
    pub fn gcd_sort(nums: Vec<i32>) -> bool {
        let mx = *nums.iter().max().unwrap() as usize;
        let mut p: Vec<usize> = (0..=mx).collect();
        fn find(p: &mut Vec<usize>, x: usize) -> usize {
            if p[x] != x { p[x] = find(p, p[x]); }
            p[x]
        }
        for &x in &nums {
            let mut y = x;
            let mut d = 2;
            while d * d <= y {
                if y % d == 0 {
                    let fx = find(&mut p, x as usize);
                    let fd = find(&mut p, d as usize);
                    p[fx] = fd;
                    while y % d == 0 { y /= d; }
                }
                d += 1;
            }
            if y > 1 {
                let fx = find(&mut p, x as usize);
                let fy = find(&mut p, y as usize);
                p[fx] = fy;
            }
        }
        let mut sorted = nums.clone();
        sorted.sort();
        for (&a, &b) in nums.iter().zip(sorted.iter()) {
            if find(&mut p, a as usize) != find(&mut p, b as usize) {
                return false;
            }
        }
        true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
  gcdSort(nums: number[]): boolean {
    const mx = Math.max(...nums);
    const p: number[] = Array.from({length: mx + 1}, (_, i) => i);
    function find(x: number): number {
      if (p[x] !== x) p[x] = find(p[x]);
      return p[x];
    }
    function factorize(x: number): number[] {
      const res: number[] = [];
      for (let d = 2; d * d <= x; d++) {
        if (x % d === 0) {
          res.push(d);
          while (x % d === 0) x = Math.floor(x / d);
        }
      }
      if (x > 1) res.push(x);
      return res;
    }
    for (const x of nums) {
      for (const f of factorize(x)) {
        p[find(x)] = find(f);
      }
    }
    const sorted = [...nums].sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i++) {
      if (find(nums[i]) !== find(sorted[i])) return false;
    }
    return true;
  }
}

Complexity

  • ⏰ Time complexity: O(n log n + n sqrt(m)), where n is the length of nums and m is the maximum value in nums, due to sorting and factorization.
  • 🧺 Space complexity: O(m), for the union-find parent array.