Leetcode 1998 GCD Sort of an Array Solution in java | Hindi Coding Community



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

class Solution {
public boolean gcdSort(int[] nums) {
for(int x: nums) {
int y = x;
for(int p=2; UF[y]==0 && p*p<=y; ++p) {
if (y % p == 0) {
union(x, p);
while(y % p == 0) y /= p;
if (y!=1) union(x, y);
int[] copy = nums.clone();
for(int i=0; i<nums.length; i++) {
if (find(nums[i])!=find(copy[i])) return false;
return true;
private int[] UF = new int[100001];
private int find(int x) {
if (UF[x]==0) return UF[x]=x;
return UF[x]==x? x: (UF[x]=find(UF[x]));
private void union(int x, int y) {
UF[find(x)] = UF[find(y)];

Post a Comment

Post a Comment (0)

#buttons=(Accept !) #days=(20)

Our website uses cookies to enhance your experience. Learn More
Accept !