Count Ancestor Pairs under a Product Bound
Updated
Problem statement
The nodes of a rooted tree are labeled 1..n, with root 1. parents[v-1] gives the parent of node v and parents[0] is zero. Count pairs (u,v) where v is a strict ancestor of u and u*v <= k. A node is not its own ancestor. Each ancestor-descendant pair is counted once.
Function
ancestorPairs(parents: int[], k: long) → longExamples
Example 1
parents = [0,1,1,2]k = 4return = 3The qualifying products are 1*2, 1*3, and 1*4; 2*4 exceeds four.
Example 2
parents = [0,1,1,2]k = 8return = 4The additional ancestor pair (4,2) meets equality.
Constraints
- For this exercise, assume a valid rooted tree with 1 <= n <= 100000 and 0 <= k <= 10^10. Return a signed 64-bit pair count.
More Intuit Online Assessment questions
- Employee Promotion OpportunitiesOA · Seen Oct 2026
- Next Pascal Row CoefficientOA · Seen Oct 2026
- Parse Router LogsOA · Seen Oct 2026
- Longest Repeated Letter Block with Adjacent SwapsOA · Seen Oct 2026
- Maximum Square-Free DivisorOA · Seen Oct 2026
- Two Tribes from Taller-Person CountsOA · Seen Oct 2026
- Shortest Path from an Encoded GraphOA · Seen Sep 2026
- Oldest and Youngest EmployeesOA · Seen Sep 2026
- Pressure-Isolation Shutdown OrderOA · Seen Sep 2026
- Submask Sum QueriesOA · Seen Sep 2026
Similar questions at other companies
- Minimum Snapshots for a Version TreeAdobe · OAAdobe interview questions
- Perfect AND Tree Leaf UpdatesPure Storage · ONSITE INTERVIEWPure Storage interview questions
- Subtree Access OverridesPinterest · PHONE SCREENPinterest interview questions
- Count Prime Values in SubtreesVisa · OAVisa interview questions
- Minimum N-ary Tree Depth DeletionsSnowflake · OA · PHONE SCREENSnowflake interview questions
- Part 1: The Narrowest KeyScale AI · OAScale AI interview questions
- Photo AlbumHonda R&D · OA
- Tree Pythagorean TriplesIBM · OAIBM interview questions
- Rolling MetricsAkuna Capital · OAAkuna Capital interview questions
- Centered Block Placement QueriesRoblox · OARoblox interview questions