Greatest Common Divisor Traversal

HARD✓ CHIP-TIMEDLC #2709 — FULL STATEMENT ↗

The drill: Two array positions are linked whenever their values share a common factor greater than 1. Decide whether every position can reach every other position by hopping across these shared-factor links.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of positive integers arrives, and two positions in it are considered linked whenever their values share a common factor greater than one.

Hopping from a position to any other position it's directly linked to, and from there to further linked positions, traces out a reachability web across the whole array.

The task is a single yes-or-no answer: can every position in the array reach every other position by hopping across these shared-factor links, however many hops it takes?

EX 01

nums = [7]

→ true

SINGLE ELEMENT, TRIVIALLY CONNECTED

EX 02

nums = [2, 3]

→ false

COPRIME PAIR, NO SHARED FACTOR

EX 03

nums = [4, 6]

→ true

DIRECT SHARED FACTOR OF 2

array length can run into the tens of thousands
values are positive integers, can repeat, and can be large
a link exists whenever two values share any prime factor
answer is boolean: fully connected or not

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

The link rule isn't about the two full values — it's about whether they share even a single prime factor. Two huge numbers are linked the instant one prime divides both.

HINT 2 THE STRUCTURE

Building the actual n² web of links and testing every pair is the honest way in, but a shared prime factor is really a hub: any two numbers that both divide by 5 are linked whether or not you ever check their gcd directly.

HINT 3 ONE STEP FROM THE ANSWER

Union-Find over the numbers AND their prime factors together: union each number's index with every prime that divides it. Numbers sharing a prime automatically land in the same set — no pairwise gcd ever needed. One connected set at the end means yes.

COACH'S BOARD — THE PATTERN, STEP BY STEP

CONNECTED BY PRIME BRIDGESPATTERN · UNION THROUGH SHARED PRIMESnums = [6, 15, 35, 77]

STEP 1

4 numbers: 6, 15, 35, 77. Two indices connect if they share a prime factor — factor each value and union its index with virtual nodes for its primes.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/greatest-common-divisor-traversal.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        n = len(nums)
        if n == 1:
            return True
        parent = {}

        def find(x):
            if x not in parent:
                parent[x] = x
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(a, b):
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb

        for i, v in enumerate(nums):
            x = v
            p = 2
            while p * p <= x:
                if x % p == 0:
                    union(i, ('p', p))
                    while x % p == 0:
                        x //= p
                p += 1
            if x > 1:
                union(i, ('p', x))

        roots = {find(i) for i in range(n)}
        return len(roots) == 1

TIME O(N·√(MAXVAL))SPACE O(N + PRIMES)PYTHON · RACE PACE · 34 LN

class Solution:
    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        n = len(nums)
        if n == 1:
            return True
        parent = list(range(n))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(a, b):
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb

        for i in range(n):
            for j in range(i + 1, n):
                if math.gcd(nums[i], nums[j]) > 1:
                    union(i, j)

        root = find(0)
        return all(find(i) == root for i in range(n))

TIME O(N²·LOG(MAXVAL))SPACE O(N)PYTHON · TRAINING PACE · 25 LN

class Solution {
    private Map<Integer, Integer> parent;

    public boolean canTraverseAllPairs(int[] nums) {
        int n = nums.length;
        if (n == 1) return true;
        parent = new HashMap<>();
        // index nodes are 0..n-1; prime nodes are offset by n+prime to avoid collision
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            int p = 2;
            while ((long) p * p <= x) {
                if (x % p == 0) {
                    union(i, n + p);
                    while (x % p == 0) x /= p;
                }
                p++;
            }
            if (x > 1) union(i, n + x);
        }
        int root = find(0);
        for (int i = 1; i < n; i++) {
            if (find(i) != root) return false;
        }
        return true;
    }

    private int find(int x) {
        parent.putIfAbsent(x, x);
        while (parent.get(x) != x) {
            parent.put(x, parent.get(parent.get(x)));
            x = parent.get(x);
        }
        return x;
    }

    private void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra != rb) parent.put(ra, rb);
    }
}

TIME O(N·√(MAXVAL))SPACE O(N + PRIMES)JAVA · RACE PACE · 41 LN

class Solution {
    private int[] parent;

    public boolean canTraverseAllPairs(int[] nums) {
        int n = nums.length;
        if (n == 1) return true;
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (gcd(nums[i], nums[j]) > 1) union(i, j);
            }
        }
        int root = find(0);
        for (int i = 1; i < n; i++) {
            if (find(i) != root) return false;
        }
        return true;
    }

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

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    private void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra != rb) parent[ra] = rb;
    }
}

TIME O(N²·LOG(MAXVAL))SPACE O(N)JAVA · TRAINING PACE · 42 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED