Skip to main content

343. Integer Break

medium

Break a positive integer n into the sum of at least two integers, maximizing their product. The DP gets it; the elegant math observation that threes win exposes the closed form.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers. Return the maximum product you can get.

Constraints

  • 2 <= n <= 58

Examples

Example 1

Input
n = 2
Output
1

Explanation: 2 = 1 + 1, 1 x 1 = 1.

Example 2

Input
n = 10
Output
36

Explanation: 10 = 3 + 3 + 4, 3 x 3 x 4 = 36.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

DP: dp[i] = max product for breaking i. Transitions: for each j in 1..i-1, dp[i] = max(dp[i], j * (i - j), j * dp[i - j]).

Hint 2

The j * (i - j) term covers 'keep i - j as a single term'; j * dp[i - j] covers 'break i - j further'.

Hint 3

Math observation: 3s give the highest product per unit. Break n into as many 3s as possible. Adjust the remainder: n % 3 == 0 -> all 3s; n % 3 == 1 -> use one 4 (= 3 + 1, but 4 > 3 * 1) and the rest 3s; n % 3 == 2 -> one 2 and the rest 3s.

Hint 4

Edge case n == 2 -> 1 and n == 3 -> 2: the problem requires at least two parts, so 2 = 1+1 -> 1 and 3 = 1+2 -> 2.

Solution approach

Reveal approach

Math closed form. For n == 2, return 1; for n == 3, return 2 (forced two-part split). Otherwise: let q = n / 3 and r = n % 3. If r == 0, return 3^q. If r == 1, return 3^(q - 1) * 4 — converting one 3 plus the remainder 1 into a single 4 (since 3 * 1 = 3 < 4). If r == 2, return 3^q * 2. O(log n) time for the exponentiation, O(1) space. DP alternative: dp[1] = 1; for i from 2 to n compute dp[i] = max over j in 1..i-1 of max(j * (i - j), j * dp[i - j]). Return dp[n]. O(n^2) time, O(n) space — easy to derive in the interview if you can't recall the math, then drop into the closed form.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • dynamic-programming
  • math
  • greedy

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

More Math practice problems

See all Math problems →