We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Integer Break

Number: 343

Difficulty: Medium

Paid? No

Companies: Google, Accenture, Microsoft, Amazon, Bloomberg, Uber, Apple

Problem Description

Given an integer n (2 <= n <= 58), break it into the sum of k positive integers (with k >= 2) such that their product is maximized. Return the maximum product that can be obtained by this break.

Key Insights

  • For maximizing product, breaking the integer into smaller parts can yield a higher product than not splitting it.
  • Greedy insight: Breaking n into as many 3's as possible generally gives the optimal solution, with adjustment for remainders (e.g. when a remainder of 1 occurs, it is beneficial to convert 3+1 into 2+2).
  • A dynamic programming approach can also be used: compute maximum products for smaller integers and build up to n by considering all partitions.
  • Be cautious with base cases (n = 2, n = 3) to ensure correctness.

Space and Time Complexity

Time Complexity: O(n^2) in the dynamic programming approach since for each integer from 2 to n, we consider all possible splits. Space Complexity: O(n) because we use an array dp of size n+1 to store intermediate results.

Solution

We can solve this problem using a dynamic programming approach. Define dp[i] to be the maximum product obtainable by breaking the integer i. For each i from 3 to n, iterate through possible first splits and update dp[i] by taking the maximum of:

  • The product of the two parts (j * (i - j))
  • The product of j and the optimal product for (i - j) stored in dp[i - j]

This covers the scenario where further breaking the second part yields a higher product.

An alternative greedy approach is based on the mathematical insight that partitioning n into as many 3's as possible (with a check on the remainder) yields the maximum product. However, the DP approach is simple and direct, especially given the constraint that n is relatively small.

Code Solutions

def integerBreak(n: int) -> int:
    # dp[i] holds the maximum product obtainable for integer i
    dp = [0] * (n + 1)
    # Base cases: for n=2 and n=3, the maximum product is defined by their splits (1*1 and 1*2).
    dp[1] = 1
    dp[2] = 1  # 2 = 1+1, product = 1 (special handling)
    
    for i in range(3, n + 1):
        # Compute dp[i] by trying all splits j and i-j
        for j in range(1, i):
            # Option 1: Do not split further the part (i - j)
            product1 = j * (i - j)
            # Option 2: Use optimum splitting for the part (i - j)
            product2 = j * dp[i - j]
            dp[i] = max(dp[i], product1, product2)
    return dp[n]

# Example usage:
print(integerBreak(10))  # Expected output: 36
← Back to All Questions