Leetcode

Integer Break

  • Time:O(n / 3)
  • Space:O(1)

C++

class Solution {
 public:
  int integerBreak(int n) {
    // If an optimal product contains a factor f >= 4, then we can replace it
    // with 2 and f - 2 without losing optimality. As 2(f - 2) = 2f - 4 >= f,
    // we never need a factor >= 4, meaning we only need factors 1, 2, and 3
    // (and 1 is wasteful).
    // Also, 3 * 3 is better than 2 * 2 * 2, so we never use 2 more than twice.
    if (n == 2)  // 1 * 1
      return 1;
    if (n == 3)  // 1 * 2
      return 2;

    int ans = 1;

    while (n > 4) {
      n -= 3;
      ans *= 3;
    }
    ans *= n;

    return ans;
  }
};

JAVA

class Solution {
  public int integerBreak(int n) {
    // If an optimal product contains a factor f >= 4, then we can replace it
    // with 2 and f - 2 without losing optimality. As 2(f - 2) = 2f - 4 >= f,
    // we never need a factor >= 4, meaning we only need factors 1, 2, and 3
    // (and 1 is wasteful).
    // Also, 3 * 3 is better than 2 * 2 * 2, so we never use 2 more than twice.
    if (n == 2)
      return 1; // 1 * 1
    if (n == 3)
      return 2; // 1 * 2

    int ans = 1;

    while (n > 4) {
      n -= 3;
      ans *= 3;
    }
    ans *= n;

    return ans;
  }
}

Python

class Solution:
  def integerBreak(self, n: int) -> int:
    if n == 2:
      return 1
    if n == 3:
      return 2

    ans = 1

    while n > 4:
      n -= 3
      ans *= 3
    ans *= n

    return ans