Domain 2MediumCORE

Integer Break

We are given an integer n and need to partition it into the sum of at least two positive integers ($k ge 2$) such that their product is maximized.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Math#Dynamic Programming

343. Integer Break

Model: qwen3.5:9b
Topics: Math,Dynamic Programming
FAANG asked: 1
Acceptance rate: 51.4%


Problem Breakdown

We are given an integer n and need to partition it into the sum of at least two positive integers (k≥2k \ge 2) such that their product is maximized.

Inputs: A single integer n. Constraints: 2≤n≤582 \le n \le 58. Outputs: The maximum possible product (integer).

Implicit constraints & tricky cases:

  1. Splitting Requirement (k≥2k \ge 2): We cannot return the number itself as a “product” of one part; we must break it down at least once. This is crucial for small inputs like n=3 or n=4.
  2. Positive Integers: The parts in the sum must be ≥1\ge 1. However, using 11 in our partition never increases the product (since multiplying by 1 doesn’t change value but consumes a unit of n). Thus, optimal partitions will generally avoid factors of 1 unless forced for small numbers.
  3. Overflow: While Python handles large integers automatically, we should be aware that intermediate products can grow significantly larger than standard 64-bit limits if nn were much larger (though here max product is manageable).

Intuition

If I start thinking about this problem from scratch:

  1. Brute Force: Try every possible partition of n and calculate the product for each. This would be exponential time complexity, which won’t pass given O(2n)O(2^n) partitions roughly.
  2. Dynamic Programming (DP): We could define a state where we compute the max product for all numbers up to n. For any number i, we try splitting it into j and i-j. This gives us an O(n2)O(n^2) solution, which is acceptable given constraints (n≤58n \le 58).
  3. Mathematical Insight: However, in a senior interview role, I’d look for the optimal mathematical property to avoid DP overhead if possible.
    • Consider factors: If we have two numbers aa and bb, their sum is constant (S=a+bS = a+b), but product P=abP = ab. The product is maximized when a≈ba \approx b (AM-GM inequality).
    • This implies our parts should be as close to each other as possible.
    • Furthermore, any number ≥5\ge 5 can be broken down into smaller factors that yield a higher product. For example, breaking 6 into 3+33+3 gives product 9 (better than keeping it or splitting differently).
    • Specifically, we want to use the factor 3 as much as possible because (n/2)k<(n/e)k(n/2)^k < (n/e)^k, and 3 is closest to Euler’s number (e≈2.718e \approx 2.718) among integers that maximize product growth per unit sum consumed.
    • So, we greedily extract factors of 3. If the remainder after dividing by 3 leaves a 0, great (all 3s). If it leaves a 1 (n%3==1n \% 3 == 1), multiplying by 11 is bad; instead, we take one ‘3’ back and combine with that ‘1’ to make two ‘2’s (since 4>3×14 > 3 \times 1, but effectively we treat the remainder as part of a larger block). If it leaves 2, just keep the single factor.

Approach

I will implement the mathematical greedy solution because it is optimal (O(1)O(1)) and demonstrates insight into number theory properties rather than relying on brute-force DP logic, though I’ll handle small inputs explicitly to satisfy the k≥2k \ge 2 constraint correctly.

Algorithm Steps:

  1. Handle base cases for n=2 (must split: 1+11+1, prod 1) and n=3 (1+21+2, prod 2). Note that standard math logic might suggest keeping them, but the problem forces a break. However, my general formula handles this if we treat small numbers carefully or just use modulo arithmetic with specific checks for remainders. Actually, to keep code clean and robust: I will calculate how many times 3 fits into n.

  2. If n%3==0n \% 3 == 0: The product is purely powers of 3 (3(n/3)3^{(n/3)}). Wait, strictly speaking for the problem constraints where we must break it? For large numbers this holds true because breaking a number like 6 into 3+33+3 yields higher product than keeping. However, there’s a nuance: if n is small (like 2 or 4), logic differs slightly from pure math formula without checks. I will use the standard pattern where we extract factors of 3 until remaining number ≤5\le 5. Correction: The most robust greedy approach for this specific problem on LeetCode involves a loop: while n > 4, multiply result by 3 and subtract 3 from n. Finally return product times remaining n. This naturally handles the k≥2k \ge 2 constraint because we stop at 4 (which breaks into 2+2=42+2=4, effectively keeping it as value but conceptually split). Wait, if I use a loop:

    • For n=5: Loop runs (5>45>4), res*=3, n becomes 2. Return res×2res \times 2. Result 1×6=61 \times 6 = 6? No wait logic check.

    Let’s refine the code strategy for clarity in explanation: I will use pow(3, (n-1)//3) style math but handle remainders explicitly to ensure correctness without a loop that might be confusing out loud. Actually, simpler is better: Use modulo arithmetic on nn.

    Refined Logic:

    • If remainder of division by 3 is 0 (n%3==0n \% 3 == 0): Product = 3(n/3)3^{(n/3)}. (Wait, for n=6 -> 9. Correct).
    • If remainder is 1: We have a ‘leftover’ 1 which we shouldn’t multiply. Instead of multiplying by (...×1)(... \times 1), we take one factor of 3 and combine with the 1 to make 2+22+2 (product 4) or just treat it as reducing count of threes by 1 and adding a ‘4’. So Product = 3(n/3)−1∗43^{(n/3)-1} * 4.
    • If remainder is 2: Just multiply remaining factor. Product = 3(n//3)∗23^{(n//3)} * 2.

    Wait, I need to check n=2 case specifically because the formula might yield incorrect results if not guarded (e.g., for n=2, rem=2 -> 30×2=23^0 \times 2 = 2, but correct answer is 1). So explicit checks for small numbers are safer.

Complexity Analysis

  • Time: O(1)O(1). We perform a constant number of arithmetic operations (modulo and power calculation), regardless of the magnitude of n within constraints. Note: In strict bit-complexity analysis, multiplication is not strictly O(1), but for interview purposes with these inputs, it’s treated as such.
  • Space: O(1)O(1). We use only a few variables to store intermediate results and counters.

Solution

import math

def integerBreak(n: int) -> int:
    # Base cases where the greedy logic needs adjustment due to k >= 2 constraint
    if n == 2: return 1
    if n == 3: return 2
    
    # We want as many factors of 3 as possible. 
    # If remainder is 0, we have all 3s (e.g., 6 -> 3*3).
    # If remainder is 1, it's better to convert a '3+1' into two '2's (product 4) than keeping the 1.
    # So if n % 3 == 1, we take one less factor of 3 and multiply by 4 instead of 3*1.
    
    remainder = n % 3
    
    count_of_threes = n // 3
    
    product = pow(3, count_of_threes)
    
    if remainder == 0:
        return product
    elif remainder == 1:
        # Convert one '3' and the '1' into two '2's (product 4). 
        # Effectively we reduce threes by 1.
        return pow(3, count_of_threes - 1) * 4
    else: # remainder == 2
        return product * 2

# Test cases from problem description logic check
print(integerBreak(2))   # Expected: 1 (Handled in base case)
print(integerBreak(10))  # Expected: 36. 
                          # n=10 -> rem=1, count_threes = 3. 
                          # Logic: pow(3, 2)*4 = 9*4 = 36. Correct.

Edge Cases Handled

  • n = 2: The code explicitly returns 1. This is critical because the mathematical formula might suggest keeping it as a factor of itself or returning 2 if not handled, but we must split into 1+11+1.
  • n = 3: Returns 2. Splitting into 1+21+2 yields product 2. The general logic for remainder handling covers this implicitly via base case check to avoid incorrect power calculations on small inputs where splitting is forced differently than large numbers.
  • Remainder Logic: Specifically handles the scenario where dividing by 3 leaves a 1