How should I practice Tree Pythagorean Triples?

Start by reading the full statement, solve the visible examples, then compare the pattern against related IBM online assessment problems in FastPrep.

Is Tree Pythagorean Triples associated with IBM?

FastPrep tags this as a IBM online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Breadth First Search

Tree Pythagorean Triples

Learn this problem

● Medium

IBMNEW GRADOA

See IBM hiring insights

Problem statement

You are given an undirected tree with vertices numbered from 1 through n, along with three fixed vertices x, y, and z.

For every vertex v, compute its unweighted edge distances to x, y, and z. Sort those three distances as a <= b <= c. Count the vertices for which all three distances are positive and a * a + b * b == c * c.

The fixed vertices may coincide. A vertex with distance zero to any of them does not contribute to the answer.

Function

countPythagoreanVertices(n: int, edges: int[][], x: int, y: int, z: int) → int

Examples

Example 1

n = 9edges = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,8],[8,9]]x = 1y = 8z = 9return = 1

Vertex 4 has distances 3, 4, and 5, so it contributes. No other vertex forms a positive Pythagorean triple.

Example 2

n = 4edges = [[1,2],[1,3],[1,4]]x = 2y = 3z = 4return = 0

The center has distances 1, 1, and 1. Every leaf has one zero distance, so the answer is zero.

Example 3

n = 13edges = [[1,2],[2,3],[3,4],[1,5],[5,6],[6,7],[7,8],[1,9],[9,10],[10,11],[11,12],[12,13]]x = 4y = 8z = 13return = 1

The three branches give the center distances 3, 4, and 5. The traversal checks every vertex rather than only the branch point.

Constraints

1 <= n <= 1000.
edges.length == n - 1.
Every edge contains two distinct vertex IDs in [1, n], and the edges form one connected tree.
1 <= x, y, z <= n; the three fixed vertices may coincide.