Integer break

Math Dynamic Programming

61.9% acceptance

Jan 12, 2026

5362

467

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.

Solution

Rust

Time O(1)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn integer_break(n: i32) -> i32 {
    if n <= 3 {
      return n - 1;
    }
    
    let quotient = n / 3;
    let remainder = n % 3;
    
    match remainder {
      0 => 3_i32.pow(quotient as u32),
      1 => 3_i32.pow((quotient - 1) as u32) * 4,
      _ => 3_i32.pow(quotient as u32) * 2,
    }
  }
}