Largest Component Size by Common Factor

This approach directly translates the problem statement into a graph data structure. It builds an explicit graph where nodes are the numbers from the input array. An edge is added between two nodes if their corresponding numbers share a common factor greater than 1. After building the graph, a standard graph traversal algorithm like Depth-First Search (DFS) or Breadth-First Search (BFS) is used to find the sizes of all connected components.

• Initialize an adjacency list to represent the graph. The nodes correspond to the indices of the nums array.
• Iterate through every unique pair of numbers (nums[i], nums[j]) from the input array.
• For each pair, calculate their Greatest Common Divisor (GCD) using the Euclidean algorithm.
• If gcd(nums[i], nums[j]) > 1, add an edge between node i and node j in the adjacency list.
• Initialize a visited array to keep track of visited nodes and a variable maxSize to store the size of the largest component found so far.
• Iterate from i = 0 to nums.length - 1. If node i has not been visited:
  • Start a DFS or BFS traversal from node i.
  • Count the number of nodes in the component discovered by the traversal.
  • Update maxSize with the maximum of its current value and the size of the new component.
• Return maxSize.

class Solution {
    public int largestComponentSize(int[] nums) {
        int n = nums.length;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (gcd(nums[i], nums[j]) > 1) {
                    adj.get(i).add(j);
                    adj.get(j).add(i);
                }
            }
        }

        boolean[] visited = new boolean[n];
        int maxSize = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                int currentSize = dfs(i, adj, visited);
                maxSize = Math.max(maxSize, currentSize);
            }
        }
        return maxSize;
    }

    private int dfs(int u, List<List<Integer>> adj, boolean[] visited) {
        visited[u] = true;
        int count = 1;
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                count += dfs(v, adj, visited);
            }
        }
        return count;
    }

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