Explanation for Integer Break


  • 0
    C

    The idea is same as this one and the answer in this one. I just write it with my style in a concise way. [At the end, it happens that it appears as same as another solution, see 1st reply below].

    1. class Solution(object):
    2.   def integerBreak(self, n):
    3.        if n < 4:
    4.            return n - 1
    5.
    6.        n3 = (n - 2) / 3
    7.        rem = (n - 2) % 3
    8.        return (3 ** n3) * (rem + 2)
    

    The maths behind the solution are re-described here:

    #1. Have been mentioned here

    Assume that n = m + (n - m) where m and (n - m) are positive numbers.

    n should be broken into numbers of 2 and 3, i.e. n = n2 * 2 + n3 * 3.

    ##Proof
    For positive integer m, to break it into 2 and m - 2 , won't decrease the product of positive integers, the sum of which is n , if 2(m - 2) >= m , i.e. m >= 4 .However, the positive numbers less than 4 include 1, 2, 3. In other word, for n, n = n1 * 1 + n2 * 2 + n3 * 3.

    • For 1, to break m into 1 and (m - 1) is useless because it doesn't increase the product.
    • For 2, as described above.
    • For 3, to break it into 3 and m - 3 , won't decrease the product , if 3(m - 3) >= m , i.e. m >= 4.5

    n2 <=2 .

    ##Proof
    For 2 + 2 + 2, we can make it as 3 + 3 where 3 * 3 > 2 * 2 * 2. Thus, n2 <= 2.

    #2. My Adaption

    n can be represented in one of following expressions:

    • n = n3 * 3 + 0 * 2
    • n = n3 * 3 + 1 * 2
    • n = n3 * 3 + 2 * 2

    They can be re-arranged as follows.

    • n = n3' * 3 + 2
    • n = n3' * 3 + 3
    • n = n3' * 3 + 4

    [Note that 4 = 2 + 2 = 2 * 2]

    Hence, line 6 in my code is used to calculate n3' and line 8 with (rem + 2) is used for the remaining part of the product, especially it happens that 4 = 2 + 2 = 2 * 2.


  • 0
    This post is deleted!

  • 0
    C

    Thank you for pointing out.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.