Tree of Coprimes - Practice Coding Problems

Tree of Coprimes - Problem

Array Math Tree Depth-First Search Number Theory Hard

There is a tree (i.e., a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. Each node has a value associated with it, and the root of the tree is node 0.

To represent this tree, you are given an integer array nums and a 2D array edges. Each nums[i] represents the ith node's value, and each edges[j] = [u_j, v_j] represents an edge between nodes u_j and v_j in the tree.

Two values x and y are coprime if gcd(x, y) == 1 where gcd(x, y) is the greatest common divisor of x and y.

An ancestor of a node i is any other node on the shortest path from node i to the root. A node is not considered an ancestor of itself.

Return an array ans of size n, where ans[i] is the closest ancestor to node i such that nums[i] and nums[ans[i]] are coprime, or -1 if there is no such ancestor.

Input & Output

Example 1 — Basic Tree

$ Input: nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]

› Output: [-1,0,0,1]

💡 Note: Node 0 is root (no ancestors). Node 1: gcd(3,2)=1, so ancestor is 0. Node 2: gcd(3,3)=3≠1 but gcd(3,2)=1, so ancestor is 0. Node 3: gcd(2,3)=1, so ancestor is 1.

Example 2 — Single Node

$ Input: nums = [5], edges = []

› Output: [-1]

💡 Note: Only one node, which is the root, so no ancestors exist.

Example 3 — Linear Chain

$ Input: nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]

› Output: [-1,0,0,1,0,0,0]

💡 Note: Complex tree structure where each node finds its closest coprime ancestor through DFS traversal.

Constraints

nums.length == n
1 ≤ n ≤ 10⁵
1 ≤ nums[i] ≤ 50
edges.length == n - 1
edges[i].length == 2
0 ≤ a_i, b_i < n
The input represents a valid tree

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Tree with nodes having values: [2,3,3,2]

Process

For each node, find closest ancestor with coprime value

Output

Array of closest coprime ancestor indices

Key Takeaway

🎯 Key Insight: Use DFS with ancestor stack to efficiently track coprime relationships during tree traversal

Asked in

G Google 25 f Facebook 18 M Microsoft 15

The key insight is to use DFS traversal while maintaining an ancestor stack organized by values. During traversal, we can quickly find the closest coprime ancestor by checking GCD with each ancestor value. Best approach is DFS with ancestor stack. Time: O(n × A × log V), Space: O(n + A) where A ≤ 50.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS with Path Reconstruction	O(n²)	O(n)	For each node, reconstruct full path to root and check each ancestor for coprimality
Optimized DFS with Ancestor Stack	O(n × A × log(max_val))	O(n + A)	Single DFS traversal maintaining ancestor stack for efficient coprime lookups

Brute Force DFS with Path Reconstruction — Algorithm Steps

Build adjacency list from edges
For each node, find path to root using DFS
Check each ancestor on path for coprimality
Return closest coprime ancestor or -1

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Tree

Create adjacency list from edges

Find Path

For each node, find complete path from root

Check Ancestors

Test each ancestor for coprimality

Code -

solution.c — C

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

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

int findPathToRoot(int** graph, int* graphSizes, int node, int parent, int target, int* path, int* pathSize) {
    path[(*pathSize)++] = node;
    if (node == target) return 1;
    
    for (int i = 0; i < graphSizes[node]; i++) {
        int neighbor = graph[node][i];
        if (neighbor != parent) {
            if (findPathToRoot(graph, graphSizes, neighbor, node, target, path, pathSize)) {
                return 1;
            }
        }
    }
    (*pathSize)--;
    return 0;
}

int* solution(int* nums, int numsSize, int** edges, int edgesSize, int* edgesColSize, int* returnSize) {
    *returnSize = numsSize;
    int* result = (int*)malloc(numsSize * sizeof(int));
    
    if (numsSize == 1) {
        result[0] = -1;
        return result;
    }
    
    // Build adjacency list
    int** graph = (int**)malloc(numsSize * sizeof(int*));
    int* graphSizes = (int*)calloc(numsSize, sizeof(int));
    
    for (int i = 0; i < numsSize; i++) {
        graph[i] = (int*)malloc(numsSize * sizeof(int));
    }
    
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1];
        graph[u][graphSizes[u]++] = v;
        graph[v][graphSizes[v]++] = u;
    }
    
    for (int i = 0; i < numsSize; i++) {
        result[i] = -1;
    }
    
    int* path = (int*)malloc(numsSize * sizeof(int));
    
    for (int i = 0; i < numsSize; i++) {
        if (i == 0) continue; // Root has no ancestors
        
        int pathSize = 0;
        findPathToRoot(graph, graphSizes, 0, -1, i, path, &pathSize);
        
        // Check ancestors from closest to farthest
        for (int j = pathSize - 2; j >= 0; j--) {
            int ancestor = path[j];
            if (gcd(nums[i], nums[ancestor]) == 1) {
                result[i] = ancestor;
                break;
            }
        }
    }
    
    // Free memory
    for (int i = 0; i < numsSize; i++) {
        free(graph[i]);
    }
    free(graph);
    free(graphSizes);
    free(path);
    
    return result;
}

int main() {
    // Simple parsing for demo - in practice would need robust JSON parsing
    int nums[] = {2, 3, 3, 2};
    int numsSize = 4;
    
    int edge0[] = {0, 1};
    int edge1[] = {1, 2};
    int edge2[] = {1, 3};
    int* edges[] = {edge0, edge1, edge2};
    int edgesSize = 3;
    int edgesColSize[] = {2, 2, 2};
    
    int returnSize;
    int* result = solution(nums, numsSize, edges, edgesSize, edgesColSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we potentially traverse up to n ancestors, and GCD calculation is O(log(min(a,b)))

⚠ Quadratic Growth

Space Complexity

O(n)

Adjacency list and recursion stack for DFS traversal

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 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

Brute Force DFS with Path Reconstruction — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler