FastPrepMinimum Cost to Merge Values into One
Problems/Minimum Cost to Merge Values into One

Minimum Cost to Merge Values into One

PayPal logoPayPal● MediumINTERNOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported as one of three questions in a PayPal software engineer intern online assessment. The task was to keep taking any two numbers out of an array and putting their sum back, where each step costs that sum, until one number is left, and to find the smallest possible total cost.

The report gives no examples and no limits. Here, an array with one value costs 0, and we use up to 10^4 values from 1 to 10^4, so the answer fits in a 32-bit integer. The function and parameter names follow the well-known stick-joining version of this task.

Our version is about 95% the same as the reported question.

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[]) → int

Examples

Example 1

sticks = [4,1,3,2]return = 19
  • Merge 1 and 2 for a cost of 3. The array becomes [4, 3, 3].
  • Merge 3 and 3 for a cost of 6. The array becomes [4, 6].
  • Merge 4 and 6 for a cost of 10. One value is left.
  • The total cost is 3 + 6 + 10 = 19. Merging from left to right instead (4 + 1, then 5 + 3, then 8 + 2) costs 5 + 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 for 10, then the other two 5s for 10, then 10 and 10 for 20.
  • The total is 10 + 10 + 20 = 40.
  • Merging the new value again right away (5 + 5, then 10 + 5, then 15 + 5) costs 10 + 15 + 20 = 45, which is more.

Constraints

  • 1 <= sticks.length <= 10^4
  • 1 <= 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

Interview reports that mention this question

  • PayPal SWE Intern OA Questions: 1 Experience
All PayPal interview questionsSee PayPal hiring insights
Saved
class Solution {
    public int connectSticks(int[] sticks) {
        // Write your code here.
    }
}
Checking account…