Compute minimal cost to merge numbers
Company: Morgan Stanley
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Given an array of positive integers, you may repeatedly perform the following operation until one number remains: choose any two numbers x and y, pay a cost of x + y, and insert x + y back into the array. Compute the minimal possible total cost. Describe the algorithm, prove why it is optimal, analyze time and space complexity, and implement it in C++. Discuss edge cases such as n = 1, duplicate values, and very large integers.
Quick Answer: Compute minimal cost to merge numbers evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Given an array of positive integers, you may repeatedly perform the following operation until exactly one number remains: choose any two numbers x and y, remove them, pay a cost of x + y, and insert the value x + y back into the array. Return the minimal possible total cost (the sum of all the per-operation costs).
This is the classic optimal-merge / Huffman problem. The optimal strategy is greedy: always merge the two smallest available numbers. Use a min-heap so each step pops the two smallest values in O(log n). Intuitively, every original value contributes to the running cost once per merge it participates in, i.e. it is charged a number of times equal to its depth in the merge tree, so keeping small values deep (merging them earliest) minimizes the weighted sum.
Edge cases:
- An empty array or a single element requires no merges, so the cost is 0.
- Duplicate values are handled naturally by the heap.
- Sums can grow large; use 64-bit integers (Python is arbitrary-precision; Java/C++ use long/long long).
Return 0 when the array has 0 or 1 elements.
Constraints
- 0 <= n (array length); return 0 when n <= 1.
- Each element is a positive integer.
- The accumulated total cost may exceed 32-bit range; use 64-bit integers in Java/C++.
- Merges continue until exactly one number remains.
Examples
Input: ([4, 3, 2, 6],)
Expected Output: 29
Explanation: Merge 2+3=5 (cost 5), then 4+5=9 (cost 9), then 6+9=15 (cost 15). Total 5+9+15 = 29.
Input: ([1, 2, 3, 4],)
Expected Output: 19
Explanation: Merge 1+2=3 (cost 3), then 3+3=6 (cost 6), then 4+6=10 (cost 10). Total 3+6+10 = 19.
Hints
- Think about how many times each original value gets added into the running cost — it equals its depth in the merge tree.
- To minimize a weighted sum where weight = depth, keep the smallest values deepest: always combine the two smallest numbers first.
- A min-heap (priority queue) lets you repeatedly extract the two smallest values in O(log n) and push their sum back.