Greatest Common Divisor Traversal - Practice Coding Problems

Greatest Common Divisor Traversal - Problem

You are given a 0-indexed integer array nums, and you are allowed to traverse between its indices. You can traverse between index i and index j, i != j, if and only if gcd(nums[i], nums[j]) > 1, where gcd is the greatest common divisor.

Your task is to determine if for every pair of indices i and j in nums, where i < j, there exists a sequence of traversals that can take us from i to j.

Return true if it is possible to traverse between all such pairs of indices, or false otherwise.

Input & Output

Example 1 — Connected Through Shared Factors

$ Input: nums = [4,3,12,8]

› Output: true

💡 Note: gcd(4,12)=4>1, gcd(12,3)=3>1, gcd(4,8)=4>1. All indices can be reached: 0↔2↔1 and 0↔3, so all pairs are traversable.

Example 2 — Disconnected Components

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

› Output: false

💡 Note: gcd(2,6)=2>1 connects indices 0 and 2, but gcd(3,2)=1 and gcd(3,6)=3>1. Index 1 connects to 2 but not 0, so we can't traverse from 0 to 1.

Example 3 — Single Element

$ Input: nums = [7]

› Output: true

💡 Note: With only one element, there are no pairs to check, so the answer is trivially true.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array of integers with their indices

GCD Connections

Find which pairs have GCD > 1

Check Connectivity

Determine if all indices are reachable

Key Takeaway

🎯 Key Insight: Use prime factorization and Union-Find to efficiently check if all indices are in the same connected component

Asked in

G Google 25 f Facebook 20 M Microsoft 15

The key insight is that two indices can be traversed if their values share a prime factor. Instead of checking all pairs, we use Union-Find with prime factorization to efficiently group connected indices. Best approach: Union-Find. Time: O(n × √M), Space: O(n + P).

Common Approaches

Approach	Time	Space	Notes
✓ Union-Find with Prime Factorization	O(n × √M)	O(n + P)	Use prime factors to group numbers and Union-Find to check connectivity efficiently
Brute Force Graph Construction	O(n²)	O(n²)	Build complete graph by checking GCD of every pair, then verify connectivity

Union-Find with Prime Factorization — Algorithm Steps

Step 1: Find all prime factors for each number
Step 2: Use Union-Find to connect indices sharing prime factors
Step 3: Check if all indices belong to the same component

Visualization

Tap to expand

Step-by-Step Walkthrough

Prime Factorization

Extract prime factors from each number

Union by Factors

Connect indices sharing prime factors

Check Connectivity

Verify all indices in same 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 n) {
    UnionFind* uf = (UnionFind*)malloc(sizeof(UnionFind));
    uf->parent = (int*)malloc(n * sizeof(int));
    uf->rank = (int*)calloc(n, sizeof(int));
    uf->size = n;
    for (int i = 0; i < n; 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), 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]++;
    }
}

void getPrimeFactors(int n, int* factors, int* count) {
    *count = 0;
    int d = 2;
    while (d * d <= n) {
        if (n % d == 0) {
            factors[(*count)++] = d;
            while (n % d == 0) n /= d;
        }
        d++;
    }
    if (n > 1) factors[(*count)++] = n;
}

bool solution(int* nums, int numsSize) {
    if (numsSize <= 1) return true;
    
    UnionFind* uf = createUF(numsSize);
    int primeToIndex[100000];
    bool primeExists[100000];
    memset(primeExists, false, sizeof(primeExists));
    
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == 1) continue;
        
        int factors[20], count;
        getPrimeFactors(abs(nums[i]), factors, &count);
        
        for (int j = 0; j < count; j++) {
            int prime = factors[j];
            if (primeExists[prime]) {
                unite(uf, i, primeToIndex[prime]);
            } else {
                primeToIndex[prime] = i;
                primeExists[prime] = true;
            }
        }
    }
    
    int nonOneIndices[1000], nonOneCount = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != 1) nonOneIndices[nonOneCount++] = i;
    }
    
    if (nonOneCount <= 1) {
        free(uf->parent);
        free(uf->rank);
        free(uf);
        return numsSize <= 1;
    }
    
    int root = find(uf, nonOneIndices[0]);
    for (int i = 1; i < nonOneCount; i++) {
        if (find(uf, nonOneIndices[i]) != root) {
            free(uf->parent);
            free(uf->rank);
            free(uf);
            return false;
        }
    }
    
    bool result = (nonOneCount == numsSize);
    free(uf->parent);
    free(uf->rank);
    free(uf);
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n × √M)

For each of n numbers, find prime factors up to √M where M is max value

✓ Linear Growth

Space Complexity

O(n + P)

Union-Find structure O(n) plus prime factor mappings O(P)

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

890 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 with Prime Factorization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler