algoadvance

Leetcode 343. Integer Break

Problem Statement

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can obtain.

Example 1:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Constraints:

Clarifying Questions

  1. Can n be 1?
    • No, n starts from 2 as per constraints.
  2. Do we need to handle any special cases?
    • Special cases involve lower values of n (like 2 and 3) where the breakdown is straightforward.

Strategy

To break down the integer n into parts that yield the maximum product, we can use mathematical insights:

  1. For integers greater than or equal to 4, breaking them into 2’s and 3’s yields a higher product.
  2. Specifically, breaking into as many 3’s as possible tends to give the optimal product, with special handling for leftovers:
    • When n % 3 == 0, it’s optimal to break entirely into 3’s.
    • When n % 3 == 1, it’s optimal to use one 2 and then continue with 3’s.
    • When n % 3 == 2, simply use the extra 2 along with the 3’s.

Code

public class Solution {
    public int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        
        int product = 1;
        while (n > 4) {
            product *= 3;
            n -= 3;
        }
        // when n is less than or equal to 4, it can only be 2, 3 or 4
        // and it is optimal to just multiply the remaining value
        return product * n;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        // Test cases
        System.out.println(sol.integerBreak(2)); // Output: 1
        System.out.println(sol.integerBreak(10)); // Output: 36
        System.out.println(sol.integerBreak(5)); // Output: 6
        System.out.println(sol.integerBreak(6)); // Output: 9
    }
}

Time Complexity

Explanation

  1. For n == 2, the only way to split is (1+1). Hence, the product is (1\times1=1).
  2. For n == 3, the only way to split is (2+1). Hence, the product is (2\times1=2).
  3. For all other n values:
    • We subtract 3 from n repeatedly (maximizing product by using as many 3’s as possible).
    • When the remaining n is less than or equal to 4, we multiply it with our product.

This mathematical insight ensures we maximize the product with the most efficient breakdowns.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI