0

Consider the following Python code that computes the minimum cost to connect sticks using a min-heap. What is the value of total_cost returned when the input is [1, 8, 3, 5]?

easy🧾 Code Trace Q12 of Q15

Greedy Algorithms - Minimum Cost to Connect Sticks

Consider the following Python code that computes the minimum cost to connect sticks using a min-heap. What is the value of total_cost returned when the input is [1, 8, 3, 5]?

A30

B36

C33

D29

Step-by-Step Solution

Solution:

Step 1: Trace initial heap and first merge
Heapify sticks: [1,3,5,8]. Pop 1 and 3 -> cost=4, total_cost=4. Push 4 back -> heap: [4,5,8]
Step 2: Trace second and third merges
Pop 4 and 5 -> cost=9, total_cost=13. Push 9 -> heap: [8,9]. Pop 8 and 9 -> cost=17, total_cost=30. Push 17 -> heap: [17]. Loop ends.
Final Answer:
Option A -> Option A
Quick Check:
Sum of merges: 4 + 9 + 17 = 30 [OK]

Quick Trick: Sum merges stepwise using min-heap pops [OK]

Common Mistakes:

MISTAKES

Adding costs incorrectly or missing last merge
Confusing heap order or popping wrong elements
Off-by-one in loop iterations

Trap Explanation:

PITFALL

Candidates often miscalculate intermediate sums or forget to add all merge costs, leading to off-by-one errors.

Interviewer Note:

CONTEXT

Tests ability to mentally execute heap-based greedy code and track cumulative cost.

Master "Minimum Cost to Connect Sticks" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions

More Greedy Algorithms Quizzes