# Explanation for Integer Break

• 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.

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.

• This post is deleted!

• Thank you for pointing out.

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