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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Integer Break and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →