Minimum Cost to Merge Values into One
Updated
Problem statement
You are given an integer array sticks of positive values. In one operation, choose any two values a and b in the array, remove both of them, and insert their sum a + b. The cost of this operation is a + b.
Keep doing operations until the array has exactly one value. Return the minimum possible total cost of all the operations. If the array already has one value, no operation is needed and the cost is 0.
Function
connectSticks(sticks: int[]) → intExamples
Example 1
sticks = [4,1,3,2]return = 19- Merge
1and2for a cost of3. The array becomes[4, 3, 3]. - Merge
3and3for a cost of6. The array becomes[4, 6]. - Merge
4and6for a cost of10. One value is left. - The total cost is
3 + 6 + 10 = 19. Merging from left to right instead (4 + 1, then5 + 3, then8 + 2) costs5 + 8 + 10 = 23.
Example 2
sticks = [7]return = 0- The array already has one value, so no operation is needed and the cost is
0.
Example 3
sticks = [5,5,5,5]return = 40- Merge two
5s for10, then the other two5s for10, then10and10for20. - The total is
10 + 10 + 20 = 40. - Merging the new value again right away (
5 + 5, then10 + 5, then15 + 5) costs10 + 15 + 20 = 45, which is more.
Constraints
1 <= sticks.length <= 10^41 <= sticks[i] <= 10^4
More PayPal interview questions
- Per-User Sliding-Window Rate LimiterOA · Seen Nov 2026
- Total Cost Against the Lowest Earlier PriceOA · Seen Nov 2026
- Items Purchase (For Java Backend Engineer)OA · Seen Nov 2024
- Find Minimum Price to SpendOA · Seen Oct 2024
- Modify ArrayOA · Seen Jun 2024
- Count User Logins 🌿 (Singapore)OA · Seen Mar 2024
- Similar Password 🪴 (Singapore)OA · Seen Mar 2024
- Can the Singer Perform the Song?PHONE SCREEN · Seen Jul 2025
Similar questions at other companies
- Maximum ScoreNVIDIA · OANVIDIA interview questions
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions
- Rearrange Songs by AuthorZomato / Eternal · OAZomato / Eternal interview questions
- Minimize the Sum with Ceiling HalvesSquarepoint Capital · OASquarepoint Capital interview questions
- Effective ManagerGoldman Sachs · OAGoldman Sachs interview questions
- Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Maximum Number of Events That Can Be AttendedByteDance · PHONE SCREENByteDance interview questions
- Minimize Total Weight After HalvingAmazon · ONSITE INTERVIEW
- Defer Expenses to Preserve BalanceDRW · PHONE SCREENDRW interview questions
- Minimize Array Sum After K Halving OperationsDocuSign · PHONE SCREENDocuSign interview questions