Tree of Coprimes

Hard

Asked by:

23 views

Topics:

TreesGraphs

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 i^th 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.

Example 1:

Input: nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
Output: [-1,0,0,1]
Explanation: In the above figure, each node's value is in parentheses.
- Node 0 has no coprime ancestors.
- Node 1 has only one ancestor, node 0. Their values are coprime (gcd(2,3) == 1).
- Node 2 has two ancestors, nodes 1 and 0. Node 1's value is not coprime (gcd(3,3) == 3), but node 0's
  value is (gcd(2,3) == 1), so node 0 is the closest valid ancestor.
- Node 3 has two ancestors, nodes 1 and 0. It is coprime with node 1 (gcd(3,2) == 1), so node 1 is its
  closest valid ancestor.

Example 2:

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,-1,0,0,0,-1]

Constraints:

nums.length == n
1 <= nums[i] <= 50
1 <= n <= 10⁵
edges.length == n - 1
edges[j].length == 2
0 <= u_j, v_j < n
u_j != v_j

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the values within the tree nodes? Can they be zero or negative?
How is the tree represented? Is it a list of edges or an adjacency list, and how are the nodes indexed?
If there are multiple nodes with a coprime value on the path to the root, which one should I return?
What should be returned if no coprime ancestor exists for a node?
What is the maximum possible depth of the tree?

Brute Force Solution

Approach

The brute force approach to this problem means checking every possible path in the tree to find the 'closest' node with a 'coprime' value. We will visit each node in the tree, comparing its value to every value of its ancestors to find the closest coprime one.

Here's how the algorithm would work step-by-step:

Start at the very first node, the root of the tree.
Look at all the nodes above it, going straight up to its parent, grandparent, and so on, all the way back to the root.
For each of those ancestor nodes, check if the current node's value and the ancestor node's value are 'coprime' which means they share no common divisors other than one.
If you find an ancestor node that is coprime, remember it as the 'closest coprime ancestor'.
Move to the next node in the tree and repeat the process: check all the nodes directly above it to find the closest coprime ancestor.
Keep doing this for every single node in the tree.
If no coprime ancestor is found for a node, mark it with a special value (like -1).
After checking every node, you will have a list that tells you, for each node, which ancestor is its closest coprime ancestor.

Code Implementation

def tree_of_coprimes_brute_force(numbers, edges):

    graph = [[] for _ in range(len(numbers))]
    for edge_start, edge_end in edges:
        graph[edge_start].append(edge_end)
        graph[edge_end].append(edge_start)

    result = [-1] * len(numbers)
    
    def gcd(first_number, second_number):
        while(second_number):
            first_number, second_number = second_number, first_number % second_number
        return first_number

    def depth_first_search(node, parent, ancestors):
        closest_coprime_ancestor = -1
        min_depth = float('inf')
        
        # Check for coprime ancestor to current node
        for depth, ancestor_value in reversed(ancestors):
            if gcd(numbers[node], ancestor_value) == 1:
                closest_coprime_ancestor = depth
                break

        if closest_coprime_ancestor != -1:
            result[node] = closest_coprime_ancestor

        new_ancestors = ancestors + [(node, numbers[node])]
        
        # Traverse the tree to find all nodes
        for neighbor in graph[node]:
            if neighbor != parent:
                depth_first_search(neighbor, node, new_ancestors)

    # Initialize DFS from the root
    depth_first_search(0, -1, [])

    return result

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm iterates through each of the n nodes in the tree. For each node, it traverses upwards to its ancestors. In the worst-case scenario, the height of the tree can be log n (for a balanced tree) or n (for a skewed tree). The algorithm performs a coprime check (GCD) for each ancestor. Since we're told it is a tree, we must assume a balanced tree. Therefore, for each node, up to log n ancestors may be checked. Thus, the overall time complexity is O(n log n).

Space Complexity

O(N) – The space complexity is dominated by the depth of the recursion stack during the traversal of the tree. In the worst-case scenario, the tree can be skewed (like a linked list), and the algorithm will recursively call itself for each node from the root to the deepest leaf. This means the maximum depth of the recursion will be N, where N is the number of nodes in the tree, resulting in N stack frames being used. Therefore, the auxiliary space is O(N).

Optimal Solution

Approach

This problem involves a family tree where each person has a value, and we want to find the closest ancestor with a value that shares no common factors with theirs. We use a technique that combines walking up the tree with pre-calculated relationships to avoid unnecessary checks.

Here's how the algorithm would work step-by-step:

Calculate the greatest common divisor between each person's value and the values of all their relatives.
As we move through the tree, keep track of all ancestors along the way, associating their values with their position in the family tree.
For each person, check their ancestors in reverse order of closeness to find the first one whose value shares no common factors with theirs.
If we can't find such an ancestor, mark this person's answer as -1.
Store the results so that each person knows which ancestor meets the condition.
Report the stored results.

Code Implementation

import math

def tree_of_coprimes(numbers, edges):
    number_of_nodes = len(numbers)
    adjacency_list = [[] for _ in range(number_of_nodes)]
    
    for edge_start, edge_end in edges:
        adjacency_list[edge_start].append(edge_end)
        adjacency_list[edge_end].append(edge_start)
    
    results = [-1] * number_of_nodes
    
    def gcd(first_number, second_number):
        while(second_number):
            first_number, second_number = second_number, first_number % second_number
        return first_number
    
    def depth_first_search(node_index, parent_node, ancestor_list):
        # Check ancestors for a coprime value.
        for ancestor_index in range(len(ancestor_list) - 1, -1, -1):
            if gcd(numbers[node_index], numbers[ancestor_list[ancestor_index][0]]) == 1:
                results[node_index] = ancestor_list[ancestor_index][0]
                break
        
        # Traverse through all neighbors.
        for neighbor_node in adjacency_list[node_index]:
            if neighbor_node != parent_node:
                # Add the current node to the ancestor list for the child.
                new_ancestor_list = ancestor_list + [(node_index, numbers[node_index])]
                depth_first_search(neighbor_node, node_index, new_ancestor_list)

    # Initiate DFS from the root (node 0) with an empty ancestor list.
    depth_first_search(0, -1, [])
    
    return results

Big(O) Analysis

Time Complexity

O(n log n) – We iterate through each of the n nodes in the tree. For each node, we traverse up the ancestor chain in the worst case, which could be of height O(log n) for a balanced tree or O(n) for a skewed tree. The gcd calculation is assumed to be O(1). Therefore, for each node, the ancestor search takes O(log n) time on average. Multiplying the cost of processing each node, we get a total time complexity of O(n log n) on average for a balanced tree and O(n^2) in the worst case for a skewed tree. Assuming balanced tree for average complexity O(n log n).

Space Complexity

O(N) – The algorithm keeps track of all ancestors along the way and their corresponding values. In the worst-case scenario, the tree can be skewed (like a linked list), leading to a maximum depth of N, where N is the number of people in the family tree. Therefore, the storage required for ancestors and their values could grow up to O(N). Additionally, the algorithm stores the results for each person, requiring an array of size N. Consequently, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array for the tree node values.	Return an empty result array or handle it as an invalid input, preventing null pointer exceptions.
The 'edges' input is null or empty, implying a single-node tree.	Initialize the result array with -1 for the single node since no parent exists.
Input edges contain cycles, forming a graph instead of a tree.	Detect cycles during graph construction and either throw an error or handle the cyclic components as independent trees.
A node has no coprime ancestor.	The result for that node should be -1 as specified in the problem description.
Large tree depth that might cause stack overflow in recursive solutions.	Convert the recursive solution to an iterative one using a stack to avoid stack overflow errors.
Integer overflow when calculating GCD for very large numbers.	Use appropriate data types (e.g., long) or bitwise GCD algorithms to prevent overflow.
All node values are the same, such as 1, which means every node is coprime to every other.	The nearest ancestor is the parent, so the answer becomes the parent in this case.
The input tree is skewed, such as a linked list represented as a tree.	The algorithm should still perform correctly but may have a higher time complexity depending on the implementation.

Null or empty input array for the tree node values.

How to Handle:

Return an empty result array or handle it as an invalid input, preventing null pointer exceptions.

The 'edges' input is null or empty, implying a single-node tree.

How to Handle:

Initialize the result array with -1 for the single node since no parent exists.

Input edges contain cycles, forming a graph instead of a tree.

How to Handle:

Detect cycles during graph construction and either throw an error or handle the cyclic components as independent trees.

A node has no coprime ancestor.

How to Handle:

The result for that node should be -1 as specified in the problem description.

Large tree depth that might cause stack overflow in recursive solutions.

How to Handle:

Convert the recursive solution to an iterative one using a stack to avoid stack overflow errors.

Integer overflow when calculating GCD for very large numbers.

How to Handle:

Use appropriate data types (e.g., long) or bitwise GCD algorithms to prevent overflow.

All node values are the same, such as 1, which means every node is coprime to every other.

How to Handle:

The nearest ancestor is the parent, so the answer becomes the parent in this case.

The input tree is skewed, such as a linked list represented as a tree.

How to Handle:

The algorithm should still perform correctly but may have a higher time complexity depending on the implementation.