Quick Overview

Minimize pairwise merge cost using a min-heap, with a greedy merge-tree proof, repeated contribution analysis, edge cases, and overflow considerations.

Minimize the Total Cost of Merging Numbers

Company: PayPal

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

Given an array of numbers, repeatedly choose two values a and b, remove them, and insert a+b. Each operation costs a+b. Find the minimum total cost needed to leave one value. ### Constraints & Assumptions Assume nonnegative integer values for the greedy solution. The source describes an integer array but does not explicitly state its sign restriction; confirm this before applying the proof. Arrays with at most one value require no merges. ### Clarifying Questions to Ask - Are all values nonnegative? - Can the cumulative cost exceed the input integer type? ```hint Count repeated contributions A value contributes to the cost every time the partial group containing it is merged again. ``` ### What a Strong Answer Covers - Choosing the two smallest current values and reinserting their sum. - A greedy argument in terms of leaf depths in the merge tree. - Heap construction, repeated extraction, total cost, and overflow. ### Follow-up Questions - How would you reconstruct the sequence of merges? - Why does repeatedly choosing the two largest values perform poorly?

Overview: Minimize pairwise merge cost using a min-heap, with a greedy merge-tree proof, repeated contribution analysis, edge cases, and overflow considerations.

Read the full PayPal Software Engineer interview experience this question came from

Given an array of nonnegative integers `numbers`, repeatedly choose two entries `a` and `b`, remove them, and insert `a + b`. That operation costs `a + b`. Return the minimum possible sum of operation costs needed to leave one value. Return `0` when the array starts with zero or one entry.

Constraints

  • numbers contains 0 through 2^31 - 1 entries.
  • Each value and the exact minimum total cost are integers from 0 to 2^53 - 1, inclusive.

Examples

Input: ([4, 3, 2, 6],)

Expected Output: 29

Explanation: Merge 2 with 3, then 4 with the resulting 5, then 6 with the resulting 9. The costs are 5, 9, and 15.

Input: ([1, 8, 3, 5],)

Expected Output: 30

Explanation: The costs are 4, 9, and 17 when the smaller values merge first.

Hints

  1. Count how often an original value contributes to the cost if the group containing it is merged several times.

Minimize the Total Cost of Merging Numbers

easyPayPalSoftware Engineer

Given an array of nonnegative integers numbers, repeatedly choose two entries a and b, remove them, and insert a + b. That operation costs a + b. Return the minimum possible sum of operation costs needed to leave one value. Return 0 when the array starts with zero or one entry.

Examples

Example 1
Input
([4, 3, 2, 6],)
Output
29
Notes
Merge 2 with 3, then 4 with the resulting 5, then 6 with the resulting 9. The costs are 5, 9, and 15.
Example 2
Input
([1, 8, 3, 5],)
Output
30
Notes
The costs are 4, 9, and 17 when the smaller values merge first.

Constraints

  • •numbers contains 0 through 2^31 - 1 entries.
  • •Each value and the exact minimum total cost are integers from 0 to 2^53 - 1, inclusive.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def minimum_merge_cost(numbers: list[int]) -> int:
Sample call
minimum_merge_cost([4, 3, 2, 6])
Language
Case 1
Input
([4, 3, 2, 6],)
Expected
29
Case 2
Input
([1, 8, 3, 5],)
Expected
30

Browse More Questions

Show the approach

Approach

Build a min-heap. Repeatedly remove the two smallest values, add their sum to the cost, and insert that sum back into the heap.

A complete merge schedule is a binary tree. Each original weight contributes once at every ancestor, so the total is the sum of each leaf weight multiplied by its depth. A deepest leaf has a leaf sibling at the same depth. In an optimal tree, the two smallest weights can be moved to that pair by swapping leaf labels. Every swap moves a smaller weight to an equal or greater depth and a larger weight to an equal or smaller depth, so the cost cannot increase.

Contract the sibling leaves into a single leaf whose weight is their sum. The cost decreases by exactly that sum. The contracted tree must be optimal for the smaller list, since otherwise replacing it would improve the original tree. This proves that merging the two smallest first is optimal, and the heap repeats that choice until one value remains.

All merge costs are nonnegative. Every new heap value and partial total is at most the final minimum, so the promised exact result range also covers the intermediates.

Time complexity:
O(n log n) for n values, with O(n) initial heap construction.
Space complexity:
O(n) auxiliary space for the heap.