# Simple Solution With Detailed Explanation, No DP Needed.

• If my calculations are right, the perfect number should be e (2.718).

However we cannot use this number.

This condition actually is much easier because all the integers larger than 3 can be broken into only 3s and 2s without 1s.
For example

``````4 = 2 + 2
5 = 3 + 2
6 = 3 + 3
...
13 = 3 + 3 + 3 + 2 + 2
``````

Whenever you combine two 3s or a 3 and a 2, the product becomes smaller. So you don't combine them.

For example:

``````16 = 3 + 3 + 3 + 3 + 2 + 2
or
16 = 6 + 6 + 2 + 2
or
16 = 6 + 5 + 5
because 6 < 3 * 3,  6 * 6 < 3 * 3 * 3 *3.
because 5 < 2 * 3,  5 * 6 < 2 * 3 * 3 *3.
``````

It is obvious you don't want a combination.

Then how many 3s you want to have?
As many as possible unless you produce a 1. If you have a 1, then substitute one 3-and-1 pair with a 2-and-2 pair.
For example:

``````7 = 3 + 3 + 1 = 3 + 2 + 2
``````

if you spare some room for 2s, the product becomes smaller again.

For example:

``````2 * 2 * 2 < 3 * 3
``````

Then the solution is simple:

1. Use as many 3 as possible
2. Avoid 1
``````class Solution(object):
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
if n == 2:
return 1
elif n == 3:
return 2
k = n / 3
m = n % 3
if m == 1:
return 4 * (3 ** (k-1))
elif m == 2:
return 2 * (3 ** k)
else:
return 3 ** k
``````

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