We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Valid Paths in a Tree

Number: 3112

Difficulty: Hard

Paid? No

Companies: Sprinklr

Problem Description

Given an undirected tree with n nodes labeled from 1 to n and an array of edges, count the number of valid paths in the tree. A path (a, b) is considered valid if the simple (non‐repeating) path from a to b contains exactly one prime number among the node labels. Note that (a, b) and (b, a) are treated as the same path.

Key Insights

  • Precompute the primality for numbers 1..n since node labels are from 1 to n.

  • If a valid path has exactly one prime, then that prime must be “unique” along the entire path. Think of it as the “center” where the rest of the path is composed entirely of nonprime nodes.

  • Remove the prime nodes from the tree to create a forest of nonprime nodes. In each connected component, no valid path (by itself) is eligible since it has zero primes.

  • For each prime node in the original tree, look at its neighboring nonprime nodes (which belong to one or more connected nonprime components) and count:

    • Valid pairs with the prime as one endpoint (p, x) where x is from one distinct connected component.
    • Valid pairs where both endpoints are nonprime but the only prime on the unique path is the prime p that connects their respective nonprime components.

  • For a prime p that touches k distinct nonprime components with sizes s1, s2, …, sk, the number of valid paths with p as the unique prime is:

    S + (S² − (s1² + s2² + … + sk²)) / 2,

    where S = s1 + s2 + … + sk.

Space and Time Complexity

Time Complexity: O(n) – Each node and edge is processed a constant number of times. Space Complexity: O(n) – For storing the tree and component information.

Solution

The solution employs the following steps:

  1. Use a sieve to precompute a boolean array indicating whether each number in 1..n is prime.
  2. Build the tree as an adjacency list.
  3. Create a “nonprime forest” by ignoring the prime nodes. For each nonprime node, perform a DFS to label its connected component and record the component’s size.
  4. For every prime node in the tree, check all its neighboring nodes. For each neighbor that is nonprime, determine which nonprime component it belongs to (ensuring that multiple edges to the same component are counted only once).
  5. Use the sizes of these distinct neighbor components to count the valid paths which have that prime as the one and only prime.
  6. Sum counts for all prime nodes to obtain the final answer.

Key Data Structures and Algorithms:

  • Sieve of Eratosthenes for prime determination.
  • Adjacency list to represent the tree.
  • Depth-first search (DFS) to identify connected components in the nonprime forest.
  • Simple arithmetic using summations to count the valid paths attached to each prime node.

Code Solutions

# Python solution with detailed comments

def countValidPaths(n, edges):
    # Step 1: Precompute primes using a sieve
    isPrime = [True] * (n + 1)
    isPrime[0] = isPrime[1] = False  # 0 and 1 are not prime
    for i in range(2, int(n**0.5) + 1):
        if isPrime[i]:
            for j in range(i*i, n+1, i):
                isPrime[j] = False

    # Step 2: Build the tree as an adjacency list
    tree = [[] for _ in range(n + 1)]
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)
    
    # Step 3: Create a nonprime forest and assign components for nonprime nodes
    compID = [0] * (n + 1)  # Component id assignment for nonprime nodes, 0 means unvisited
    compSize = {}
    currentID = 0

    def dfs(node, cid):
        # DFS that marks all nonprime nodes connected to 'node' with component id 'cid'
        stack = [node]
        compID[node] = cid
        size = 0
        while stack:
            cur = stack.pop()
            size += 1
            for neighbor in tree[cur]:
                # Only traverse to neighbor if it is nonprime and not yet visited
                if not isPrime[neighbor] and compID[neighbor] == 0:
                    compID[neighbor] = cid
                    stack.append(neighbor)
        return size

    # Run DFS for each nonprime node that is not yet visited.
    for node in range(1, n + 1):
        if not isPrime[node] and compID[node] == 0:
            currentID += 1
            size = dfs(node, currentID)
            compSize[currentID] = size

    # Step 4: For every prime node, inspect adjacent nonprime components and count valid paths
    validPathsCount = 0
    for node in range(1, n + 1):
        if isPrime[node]:
            # Set to collect distinct neighbor component ids
            neighborComponents = {}
            for neighbor in tree[node]:
                # If neighbor is nonprime, add its component id if exists
                if not isPrime[neighbor]:
                    cid = compID[neighbor]
                    neighborComponents[cid] = compSize[cid]
            # If there are no adjacent nonprime components, skip counting for this prime node.
            if not neighborComponents:
                continue
            sizes = list(neighborComponents.values())
            S = sum(sizes)
            sumSq = sum(s * s for s in sizes)
            # Count valid pairs: paths where one endpoint is the prime node and the other is nonprime
            # plus pairs of nonprime endpoints coming from different components
            countForPrime = S + (S * S - sumSq) // 2
            validPathsCount += countForPrime

    return validPathsCount

# Example Usage:
n1 = 5
edges1 = [[1,2],[1,3],[2,4],[2,5]]
print(countValidPaths(n1, edges1))  # Expected output: 4

n2 = 6
edges2 = [[1,2],[1,3],[2,4],[3,5],[3,6]]
print(countValidPaths(n2, edges2))  # Expected output: 6
← Back to All Questions