Integer Break
Real-world version: Cut the Rod for the Largest ProductThe statement here is our own: the same inputs, outputs and technique.
A supplier holds a single rod of length n centimetres and has to saw it into two or more pieces. Every piece must be a whole number of centimetres long, and the piece lengths have to add up to exactly n. Pieces may repeat a length, and their order does not matter.
The pieces are then sold as a set priced at the product of their lengths. Return the largest product any allowed set of pieces can reach.
Examples
Example 1
- Input
- n = 7
- Output
- 12
Cutting the rod into pieces of 3 and 4 gives lengths that add to 7 and a product of 12.
Example 2
- Input
- n = 4
- Output
- 4
Cutting into 2 and 2 gives a product of 4, and the two pieces add up to 4.
Example 3
- Input
- n = 43
- Output
- 6377292
One allowed set is thirteen pieces of 3 and one piece of 4, which add up to 43 and multiply to 6377292.
Constraints
- 2 <= n <= 58
- The answer never exceeds 1549681956.
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 integer_break(n: int) -> int:public int integerBreak(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