GCD Sort of an Array - Practice Coding Problems

GCD Sort of an Array - Problem

Array Math Union Find Sorting Number Theory Hard

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.

Input & Output

Example 1 — Numbers with Common Factors

$ Input: nums = [7,21,3]

› Output: true

💡 Note: We can swap 21 and 3 since gcd(21,3) = 3 > 1, giving us [7,3,21]. This is sorted in non-decreasing order.

Example 2 — Numbers without Sufficient Connections

$ Input: nums = [5,2,6,2]

› Output: false

💡 Note: gcd(5,2)=1, gcd(5,6)=1, gcd(2,6)=2>1, gcd(2,2)=2>1. The 5 cannot be moved from position 0, but it needs to be at position 2 in the sorted array [2,2,5,6].

Example 3 — Already Sorted

$ Input: nums = [10,5,9,3,15]

› Output: false

💡 Note: gcd(10,5)=5>1, gcd(9,3)=3>1, gcd(9,15)=3>1, gcd(3,15)=3>1. However, the components are [10,5] and [9,3,15]. Number 5 needs to be at position 1 in sorted array [3,5,9,10,15], but it can only reach positions in component with 10.

Constraints

1 ≤ nums.length ≤ 3 × 10⁴
2 ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array [7,21,3] with GCD connections between pairs

Find Connections

gcd(21,3) = 3 > 1, so 21 and 3 can be swapped

Result

After swap: [7,3,21] which is sorted

Key Takeaway

🎯 Key Insight: Numbers can only be rearranged within their connected components formed by GCD > 1 relationships

Asked in

G Google 12 F Facebook 8

The key insight is that numbers can only be swapped if their GCD > 1, creating connected components. Each number must be able to reach its target sorted position within its connected component. The optimal approach uses Union-Find to efficiently identify these components and verify sortability. Time: O(n² × log(max)), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Union-Find Connected Components	O(n² × log(max))	O(n)	Use Union-Find to group numbers that can be swapped, then check if each number can reach its sorted position
Brute Force Simulation	O(n³ × log(max))	O(n)	Repeatedly try all possible swaps until array is sorted or no more swaps are possible

Union-Find Connected Components — Algorithm Steps

Create Union-Find structure and connect numbers with GCD > 1
For each pair of numbers, if GCD > 1, union them
Check if each number and its target position belong to same component
Return true only if all numbers can reach their target positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Find GCD Connections

Connect numbers with GCD > 1

Build Components

Group connected positions into components

Validate Sorting

Check if each number can reach target position in its component

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int* parent;
    int* rank;
    int size;
} UnionFind;

UnionFind* createUF(int size) {
    UnionFind* uf = (UnionFind*)malloc(sizeof(UnionFind));
    uf->parent = (int*)malloc(size * sizeof(int));
    uf->rank = (int*)calloc(size, sizeof(int));
    uf->size = size;
    for (int i = 0; i < size; i++) {
        uf->parent[i] = i;
    }
    return uf;
}

int find(UnionFind* uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

void unite(UnionFind* uf, int x, int y) {
    int px = find(uf, x);
    int py = find(uf, y);
    if (px == py) return;
    
    if (uf->rank[px] < uf->rank[py]) {
        uf->parent[px] = py;
    } else if (uf->rank[px] > uf->rank[py]) {
        uf->parent[py] = px;
    } else {
        uf->parent[py] = px;
        uf->rank[px]++;
    }
}

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

bool solution(int* nums, int n) {
    int* sortedNums = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        sortedNums[i] = nums[i];
    }
    qsort(sortedNums, n, sizeof(int), compare);
    
    UnionFind* uf = createUF(n);
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (gcd(nums[i], nums[j]) > 1) {
                unite(uf, i, j);
            }
        }
    }
    
    // Simple check: for each position, verify if current and target values
    // can be in same position (same component)
    for (int i = 0; i < n; i++) {
        int targetVal = sortedNums[i];
        bool canPlace = false;
        
        for (int j = 0; j < n; j++) {
            if (nums[j] == targetVal && find(uf, i) == find(uf, j)) {
                canPlace = true;
                break;
            }
        }
        
        if (!canPlace) {
            free(sortedNums);
            free(uf->parent);
            free(uf->rank);
            free(uf);
            return false;
        }
    }
    
    free(sortedNums);
    free(uf->parent);
    free(uf->rank);
    free(uf);
    return true;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[],\n");
    
    while (token != NULL) {
        if (strlen(token) > 0) {
            nums[n++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    bool result = solution(nums, n);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × log(max))

O(n²) pairs to check GCD, each GCD takes O(log(max)), Union-Find operations are nearly O(1)

⚠ Quadratic Growth

Space Complexity

O(n)

Union-Find parent array and rank array of size n

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Union-Find Connected Components — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler