Greatest Common Divisor Traversal

NeetCode: Greatest Common Divisor Traversal · LeetCode: 2709. Greatest Common Divisor Traversal · Difficulty: Hard

Given an integer array nums, you may travel between indices i and j (i != j) if gcd(nums[i], nums[j]) > 1. Return true if for every pair of indices there is a sequence of such moves connecting them, otherwise false.

Example

Text

Input:  nums = [2, 3, 6]        Output: true    (2-6 share 2, 3-6 share 3)
Input:  nums = [3, 9, 5]        Output: false   (5 is isolated)
Input:  nums = [4, 3, 12, 8]    Output: true

Brute force: gcd of every pair

Treat indices as graph vertices with an edge whenever the gcd of two values is above 1, then check that the graph is connected. Union-find merges each connected pair; at the end, every index must share one root.

This computes n^2 / 2 gcds, each O(log M) for the largest value M. With n up to 10^5 that is around 5 * 10^9 gcd calls, which is far too slow.

Java

class Solution {
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

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

    public boolean canTraverseAllPairs(int[] nums) {
        int n = nums.length;
        int[] 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) {
                    parent[find(parent, i)] = find(parent, j);
                }
            }
        }
        int root = find(parent, 0);
        for (int i = 1; i < n; i++) {
            if (find(parent, i) != root) return false;
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.canTraverseAllPairs(new int[] {2, 3, 6}));
        System.out.println(s.canTraverseAllPairs(new int[] {3, 9, 5}));
        System.out.println(s.canTraverseAllPairs(new int[] {4, 3, 12, 8}));
        System.out.println(s.canTraverseAllPairs(new int[] {1}));
        System.out.println(s.canTraverseAllPairs(new int[] {1, 1}));
    }
}

Output

true
false
true
true
false

Time: O(n^2 * log M). Space: O(n).

Optimal: union-find over prime factors

Two numbers share a common divisor above 1 exactly when they share a prime factor. So instead of comparing numbers with each other, record for each prime the first index whose number has it. When a later number has the same prime, union the two indices. Two indices end up in the same set if and only if a chain of shared primes links them, which is the traversal rule. The answer is true when exactly one component remains.

Steps: return true for n == 1 and false if a longer array contains a 1 (it has no prime factors); build a smallest-prime-factor table up to the largest value with a sieve, so each number factors in O(log M); for each prime factor of a number, union its index with the first index that had the prime; count components.

The table is an int[] of size max + 1, so the sieve assumes max is small enough to allocate and for p * p to fit in int. LeetCode limits values to 10^5.

Java

import java.util.Arrays;

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

    public boolean canTraverseAllPairs(int[] nums) {
        int n = nums.length;
        if (n <= 1) return true;
        int max = 0;
        for (int value : nums) {
            if (value == 1) return false; // 1 has no prime factors, so it can never move
            max = Math.max(max, value);
        }

        // spf[x] is the smallest prime factor of x.
        int[] spf = new int[max + 1];
        for (int i = 0; i <= max; i++) spf[i] = i;
        for (int p = 2; p * p <= max; p++) {
            if (spf[p] == p) {
                for (int multiple = p * p; multiple <= max; multiple += p) {
                    if (spf[multiple] == multiple) spf[multiple] = p;
                }
            }
        }

        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        int[] firstWith = new int[max + 1]; // prime -> first index having it
        Arrays.fill(firstWith, -1);
        int components = n;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            while (x > 1) {
                int p = spf[x];
                while (x % p == 0) x /= p;
                if (firstWith[p] == -1) {
                    firstWith[p] = i;
                } else {
                    int a = find(parent, i), b = find(parent, firstWith[p]);
                    if (a != b) {
                        parent[a] = b;
                        components--;
                    }
                }
            }
        }
        return components == 1;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.canTraverseAllPairs(new int[] {2, 3, 6}));
        System.out.println(s.canTraverseAllPairs(new int[] {3, 9, 5}));
        System.out.println(s.canTraverseAllPairs(new int[] {4, 3, 12, 8}));
        System.out.println(s.canTraverseAllPairs(new int[] {1}));
        System.out.println(s.canTraverseAllPairs(new int[] {1, 1}));
    }
}

Output

true
false
true
true
false

Trace of [2, 3, 6]: index 0 stores prime 2, index 1 stores prime 3, and index 2 (value 6) meets prime 2 (union with 0) and prime 3 (union with 1), leaving one component. Time: O(M log log M + n log M) for the sieve and the factorizations, plus near-constant union-find work per prime. Space: O(M + n).

Factoring each number by trial division up to its square root needs no table and costs O(sqrt(M)) per number, about 3 * 10^7 steps for n = M = 10^5; the sieve version is asymptotically faster.

How to explain it in an interview

Brute force: take the gcd of every pair and union indices with gcd above 1, then check for one component. That is O(n^2 log M), too slow for n = 10^5.
Key idea: sharing a divisor above 1 means sharing a prime, so link each index to its primes instead of to other indices.
Steps: (1) edge cases: n == 1 is true, any 1 in a longer array is false; (2) build a smallest-prime-factor sieve; (3) factor each number and keep, per prime, the first index that had it; (4) union the current index with that index for every repeated prime; (5) return whether one component is left.
Complexity: time O(M log log M + n log M), space O(M + n).
Pitfalls: a single-element array is true even if the value is 1; a 1 in a longer array is isolated.