FastPrepCount Prime Values in Subtrees
Problems/Count Prime Values in Subtrees

Count Prime Values in Subtrees

Visa logoVisa● MediumFULLTIMEOA
QuestionFunctionExamplesConstraints

Problem statement

Source note: You count, for each queried node of a rooted tree, the nodes at or below it that hold a prime number. It was one of two tree questions in a 90-minute Visa online assessment; the report does not describe the real-world scenario around them.

The report gives no input format, examples or limits. Practice choices here: the tree is an undirected edge list rooted at node 0, a node's subtree includes the node itself, values are integers from 1 to 10^6 and 1 is not prime, the answer holds one count per query in the same order as the queries, and the limits and examples are ours.

The judged task matches the report at about 75%.

A tree has n nodes numbered 0 to n - 1 and is rooted at node 0. Each edge [u, v] in edges connects u and v; the two ends may be listed in either order. Node i holds the value values[i].

The subtree of a node is the node itself together with all of its descendants. For each query node queries[j], count the nodes in its subtree whose value is a prime number. A prime number is an integer greater than 1 whose only positive divisors are 1 and itself, so 1 is not prime.

Return an array whose j-th entry is the count for queries[j].

Function

countPrimesInSubtrees(n: int, edges: int[][], values: int[], queries: int[]) → int[]

Examples

Example 1

n = 5edges = [[0,1],[0,2],[1,3],[1,4]]values = [2,4,3,5,1]queries = [0,1,2,4]return = [3,1,1,0]
  • Node 0 is the root, so its subtree is the whole tree with values 2, 4, 3, 5, 1. The primes are 2, 3 and 5: 3.
  • The subtree of node 1 is nodes 1, 3, 4 with values 4, 5, 1. Only 5 is prime: 1.
  • The subtree of node 2 is just node 2 with value 3: 1.
  • The subtree of node 4 is node 4 with value 1, and 1 is not prime: 0.

Example 2

n = 4edges = [[2,0],[3,2],[1,3]]values = [7,11,9,13]queries = [3,2,0]return = [2,2,3]

The edges can be listed in either direction. Rooted at 0, the tree is the path 0 - 2 - 3 - 1. The subtree of node 3 holds nodes 3 and 1 (values 13 and 11, both prime): 2. Node 2 adds value 9 = 3 · 3, which is not prime: still 2. Node 0 adds the prime 7: 3.

Example 3

n = 1edges = []values = [1]queries = [0,0]return = [0,0]

A single node with value 1. The number 1 is not prime, so both queries answer 0.

Constraints

  • 1 <= n <= 5000
  • edges.length == n - 1, each edge is [u, v] with 0 <= u, v < n and u != v, and the edges form a tree.
  • values.length == n
  • 1 <= values[i] <= 10^6
  • 1 <= queries.length <= 5000
  • 0 <= queries[j] < n

More Visa problems

  • Minimum-Sum Tree Fill with Unit StepsOA · Seen Nov 2026
  • House RobberPHONE SCREEN · Seen Nov 2026
  • House Robber IIIPHONE SCREEN · Seen Nov 2026
All Visa interview questionsSee Visa hiring insights
Saved
class Solution {
    public int[] countPrimesInSubtrees(int n, int[][] edges, int[] values, int[] queries) {
        // Write your code here.
    }
}
Checking account…