Minimum Cost to Split into Ones
Real-world version: Cheapest Way to Break a Pile DownThe statement here is our own: the same inputs, outputs and technique.
A single pile holds n tokens.
One break takes a pile holding at least two tokens and divides it into two piles, each holding at least one token, at a cost equal to the size of the pile being broken. Breaks continue until every pile holds a single token.
Return the least total cost of getting there.
Examples
Example 1
- Input
- n = 7
- Output
- 20
Breaking the seven into three and four costs 7. The three then costs 5 and the four costs 8, coming to 20. Peeling single tokens off instead would cost 7 plus 6 plus 5 plus 4 plus 3 plus 2, which is 27.
Example 2
- Input
- n = 1
- Output
- 0
The pile already holds a single token, so nothing needs breaking.
Example 3
- Input
- n = 8
- Output
- 24
Halving all the way down costs 8, then two piles of four at 4 each, then four piles of two at 2 each, coming to 24.
Constraints
- 1 <= n <= 500
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def min_cost(n: int) -> int:public int minCost(int n)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's