How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Bytedance.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Bytedance during technical interviews.

Minimize Increments to Equalize Path Costs

Q: Minimize Increments to Equalize Path Costs

This question evaluates understanding of tree data structures, root-to-leaf path aggregation, and cost-balancing strategies within the Coding & Algorithms domain.

Company: Bytedance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a perfect binary tree with `n` nodes, labeled from `1` to `n` in level-order. For any non-leaf node `i`, its left child is `2 * i` and its right child is `2 * i + 1`. Each node `i` has a positive integer cost `cost[i - 1]`. A root-to-leaf path cost is the sum of the costs of all nodes on that path. In one operation, you may choose any node and increase its cost by `1`. Return the minimum number of operations needed so that every root-to-leaf path has the same total cost. Constraints: - `1 <= n <= 10^5` - `n` represents a perfect binary tree, so `n = 2^h - 1` for some integer `h >= 1` - `1 <= cost[i] <= 10^4` Example: ```text Input: n = 7 cost = [1, 5, 2, 2, 3, 3, 1] Tree: 1 / \ 5 2 / \ / \ 2 3 3 1 Output: 6 ``` Explanation: The root-to-leaf path sums are: - `1 + 5 + 2 = 8` - `1 + 5 + 3 = 9` - `1 + 2 + 3 = 6` - `1 + 2 + 1 = 4` By incrementing selected node costs, all root-to-leaf path sums can be made equal using a minimum of `6` total increments.

Quick Answer: This question evaluates understanding of tree data structures, root-to-leaf path aggregation, and cost-balancing strategies within the Coding & Algorithms domain.

You are given a perfect binary tree with n nodes, labeled from 1 to n in level-order. For any non-leaf node i, its left child is 2 * i and its right child is 2 * i + 1. Each node i has a positive integer cost stored in cost[i - 1]. A root-to-leaf path cost is the sum of the costs of all nodes on that path. In one operation, you may choose any node and increase its cost by 1. Return the minimum number of operations needed so that every root-to-leaf path has the same total cost.

Constraints

1 <= n <= 10^5
n = 2^h - 1 for some integer h >= 1
len(cost) == n
1 <= cost[i] <= 10^4

Examples

Input: (7, [1, 5, 2, 2, 3, 3, 1])

Expected Output: 6

Explanation: At node 2, its children differ by 1; at node 3, its children differ by 2; after that, the two subtrees under the root differ by 3. Total operations = 1 + 2 + 3 = 6.

Input: (1, [7])

Expected Output: 0

Explanation: There is only one root-to-leaf path, so all path costs are already equal.

Input: (7, [1, 2, 3, 4, 5, 6, 7])

Expected Output: 5

Explanation: Balance the children of node 2 with 1 increment, balance the children of node 3 with 1 increment, then balance the two subtrees at the root with 3 more increments.

Input: (15, [1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2])

Expected Output: 4

Explanation: Each leaf pair under nodes 4, 5, 6, and 7 differs by 1, so 4 operations make all four lower subtrees balanced. Higher levels are then already balanced.

Input: (7, [4, 2, 2, 1, 1, 1, 1])

Expected Output: 0

Explanation: All root-to-leaf path sums are already 7, so no increments are needed.

Hints

Work from the bottom of the tree upward. For each parent, compare the best path sum coming from its left child and right child.
If one subtree path sum is smaller, you must add exactly the difference to that subtree. After balancing, the parent contributes its own cost plus the larger of the two child path sums.

Quick Overview

This question evaluates understanding of tree data structures, root-to-leaf path aggregation, and cost-balancing strategies within the Coding & Algorithms domain.