FastPrepCheapest Order to Cut a Rod
Problems/Cheapest Order to Cut a Rod

Cheapest Order to Cut a Rod

Adobe logoAdobe● HardFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: This problem asks for the cheapest order of cuts on a rod when each cut costs the length of the piece it splits. The report mentions it only in passing: an Adobe CS-1 interviewer raised it in the first round and changed the question once the candidate recognised it, so the report gives no statement, limits or examples for it.

Our choices: the usual rules with the cutting order left free, a rod of length up to 10^6, at most 100 different cut positions, and new examples.

The judged task matches the report at about 75%.

A wooden rod has length n, with marks at positions 0 to n. You must cut it at every position listed in cuts, one cut at a time, in any order you like.

A cut always splits one piece into two, and it costs the length of the piece being cut at that moment. For example, the first cut always costs n.

Return the smallest possible total cost of making all the cuts.

Function

minCutCost(n: int, cuts: int[]) → int

Examples

Example 1

n = 10cuts = [2,7,8]return = 20

Cut at 7 first (cost 10), leaving pieces 0-7 and 7-10. Then cut 0-7 at 2 (cost 7) and 7-10 at 8 (cost 3). The total is 10 + 7 + 3 = 20. Cutting at 2 first would cost 10 + 8 + 6 = 24 or 10 + 8 + 3 = 21 at best.

Example 2

n = 5cuts = [3]return = 5

One cut on a rod of length 5 always costs 5.

Example 3

n = 12cuts = [1,2,3,9,10,11]return = 31

Cut at 3 and 9 first to split off the two crowded ends: 12 + 9 = 21. Each end piece of length 3 then needs two cuts costing 3 + 2 = 5, so the total is 21 + 5 + 5 = 31.

Constraints

  • 2 <= n <= 10^6
  • 1 <= cuts.length <= min(n - 1, 100)
  • 1 <= cuts[i] <= n - 1, and all values in cuts are different

More Adobe problems

  • Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
  • All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
  • Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
All Adobe interview questionsSee Adobe hiring insights
Saved
public int minCutCost(int n, int[] cuts) {
    // Write your code here.
}
Checking account…