A foundry has cast one ingot of integer mass n and must reduce it to n separate unit ingots (mass 1 each) before it can be sent on to the molds. The only allowed operation is to take any ingot currently on the floor whose mass is more than 1 and break it into two smaller ingots of positive integer mass that add up to its original mass — any split point is allowed. Every break requires reheating the whole ingot first, so a break costs a fee equal to the mass of the ingot being broken, no matter how the resulting two masses are chosen. The foundry keeps breaking ingots, in any order, until every ingot on the floor has mass exactly 1. Find the minimum total fee needed to reach that state.
A single line containing one integer n.
A single integer: the minimum total fee.
Example 1
Input
4
Expected
8
Explanation
Break the mass-4 ingot into two mass-2 ingots (fee 4), then break each mass-2 ingot into two mass-1 ingots (fee 2 each). Total fee = 4 + 2 + 2 = 8. Breaking it unevenly first, e.g. into masses 1 and 3, costs 4 for that break plus 5 more to finish reducing the mass-3 piece (3 + 0 + 2), for 9 total — worse.
Example 2
Input
5
Expected
12
Explanation
Break the mass-5 ingot into masses 2 and 3 (fee 5). Break the mass-2 piece into two mass-1 ingots (fee 2). Break the mass-3 piece into masses 1 and 2 (fee 3), then break that resulting mass-2 piece into two mass-1 ingots (fee 2). Total fee = 5 + 2 + 3 + 2 = 12.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →