GCD Sort of an Array

Challenge Points: 30

Level: Hard

You are given an integer array nums. You are allowed to perform this special operation any number of times:

Pick two indices i and j and swap nums[i] with nums[j] only if
gcd(nums[i], nums[j]) > 1
(i.e., the two numbers share a common factor greater than 1).

Your task is to determine whether it is possible to rearrange the array into non-decreasing order by using only these gcd-based swaps.

If sorting is achievable → return true, otherwise → return false.

Input: nums = [12, 6, 9]

Output: true

Explanation:

gcd(12, 6) = 6 → can swap gcd(6, 9) = 3 → can swap So full sorting is possible.

Input: nums = [11, 7, 13]

Output: false

Explanation:

All numbers are prime and share no common factor > 1. No swaps are allowed → cannot sort.

Input: nums = [4, 3, 6, 9]

Output: true

Explanation:

gcd(4, 6) = 2 gcd(6, 9) = 3 With these valid swaps, sorted order is possible.

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result