343.Integer Break

Tags: [math]

Link: https://leetcode.com/problems/integer-break/\#/description

Given a positive integern, break it into the sum ofat leasttwo positive integers and maximize the product of those integers. Return the maximum product you can get.

For example, givenn= 2, return 1 (2 = 1 + 1); givenn= 10, return 36 (10 = 3 + 3 + 4).

Note: You may assume thatnis not less than 2 and not larger than 58.

Hint:

1. There is a simple O(n) solution to this problem.
2. You may check the breaking results of n ranging from 7 to 10 to discover the regularities.

Solution: math

class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 2:
            raise ValueError('The input is invalid')

        if n == 2:
            return 1
        if n == 3:
            return 2
        if n == 4:
            return 4

        product = 1
        while n > 4:
            product *= 3
            n -= 3

        product *= n
        return product

Revelation:

• Think if we just break one number n to two parts x and (n - x). The product = x * (n - x) = -x^2 + n*x. The curve is y = -x^2 + n*x.

• Let y = 0, so -x^2 + n*x = 0, so x^2 - n*x = 0. x1 = 0 and x2 = n. So we can draw this curve, like following:

• So when x = n/2, the y get the max value. and max y = (n^2) / 4.

• Let max_y > n, which means let two parts' product > n, so (n^2) / 4 >= n, so we can get n > 4, which means when n > 4, we can break n to get a product which is greater than n.
• For the integer n which is strictly greater than 4, it has a property: 3 * (n - 3) > n. To prove this: 3 * (n - 3) > n, 3n - 9 > n, 4*n> 9, because n is integer, so n > 4.
• So each time we try our best to break the n to 3 and n - 3, then do iteration, until the remaining part of n is <= 4.

Note:

• Time complexity = O(n).

Time Limited Exceeded

class Solution(object):

    def __init__(self):
        self. max_product = 1

    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 2:
            raise ValueError('The input is invalid')

        for num_of_breaks in xrange(2, n + 1):
            breaks = []
            self.integer_break_helper(n, num_of_breaks, 0, breaks)

        return self.max_product

    def integer_break_helper(self, n, num_of_breaks, index, breaks):
        # base case
        if len(breaks) > num_of_breaks or index > n:
            return

        if index == n and len(breaks) == num_of_breaks:
            product = 1
            for sub_sum in breaks:
                product *= sub_sum
            self.max_product = max(self.max_product, product)
            return

        for i in xrange(index, n):
            sub_sum = i - index + 1

            breaks.append(sub_sum)
            self.integer_break_helper(n, num_of_breaks, i + 1, breaks)
            breaks.pop()


if __name__ == '__main__':
    print 'Program is working'

    # n = 2
    # n = 4
    # n = 7
    # n = 8
    # n = 9
    n = 10
    solution = Solution()
    print solution.integerBreak(n)

    print 'Program is end'

Revelation:

• Brute force: Try all possible ways to break the n.

Note:

• Time complexity = O(n^(n - 1) + n^(n - 2) + n^(n - 3) + ... + n^1) = O(n^1 + n^2 + n^3 + ... + n^(n - 1)). This is a geometric sequence(等比数列). sum = a1 * (1 - q^N) / (1 - q), so here a1 = n^1, q = n, N = n - 1. So the time complexity = O(n * (1 - n^(n - 1)) / (1 - n)) = O(n^n).
• Explanation of why time complexity is O(n^(n - 1) + n^(n - 2) + n^(n - 3) + ... + n^1) = O(n^1 + n^2 + n^3 + ... + n^(n - 1)). Think we can break the k parts, so there will be k - 1 pointers to split the n into k parts. and each pointer can be a "loop". For example we want to break n to 4 parts, so there will be 3 pointers to split n. If we try all possible ways to break n by 3 pointers, that time complexity should be O(n^3), so if we want to break the n into k parts, the time complexity = O(n^k). And for this Leetcode question, k can be 2, 3, 4, ...., n.