Integer Break

Integer Break is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (Fibonacci Style) subpattern.

Problem statement

Given the integer n, split it into the sum of at least two positive integers. The parts may be equal, and their order does not affect the result. The product of a split is the multiplication of all its parts.

Implement Solution.integerBreak, which receives n and determines the greatest product obtainable from any valid split.

Return that maximum product as a JSON integer.

Example 1:

Input: n = 4 Output: 4 Explanation: The best split is 2 + 2, whose product is 4; splitting into 1 + 3 produces only 3.

Example 2:

Input: n = 6 Output: 9 Explanation: The split 3 + 3 gives product 9, which is larger than the products from the other valid splits.

Example 3:

Input: n = 11 Output: 54 Explanation: The split 3 + 3 + 3 + 2 sums to 11 and has product 54, the greatest possible product.

Constraints:

- 2 <= n <= 58 - n is an integer. - Every part used in a split must be a positive integer. - A valid split contains at least two parts whose sum is exactly n. - The maximum product fits in a 32-bit signed integer.

Topics and companies

Topics: Dynamic Programming, Math, Enumeration.

How to practise Integer Break on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n^2) time and O(n) space.

Open Integer Break in the code editor, or read the Integer Break editorial for a worked solution with its approach and complexity analysis.

Where Integer Break sits in the DSA pattern sheet

Problems related to Integer Break

Other problems that use the same 1D Array (Fibonacci Style) and Dynamic Programming (DP) Patterns techniques:

Preparing this workspace.