Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

343. Integer Break

Time: $O(n / 3)$

Space: $O(1)$

			


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;
  }
};




			


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;
  }
}




			


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