If we want to break a number, breaking it into 3s turns out to be the most efficient.
2^3 < 3^2
4^3 < 3^4
5^3 < 3^5
6^3 < 3^6
...
Therefore, intuitively, we want as many 3 as possible
if a number % 3 == 0, we just break it into 3s > the product is Math.pow(3, n/3)
As for numbers % 3 == 1, we don't want the 'times * 1' in the end;
borrowing a 3 is a natural thought.
if we borrow a 3, 3 can be divided into
case 1: 1 + 2 > with the extra 1, we have 2*2 = 4
case 2: (0) + 3 > with the extra 1, we have 4
turns out these two cases have the same results
so, for numbers % 3 == 1 > the result would be Math.pow(3, n/31)*4
Then we have the numbers % 3 == 2 left
again, we try to borrow a 3,
case 1: 1+2 > with the extra 2, we have 1*5 or 3*2 => 3*2 is better
case 2: 0+3 > with the extra 2, we have 2*3 or 5 => 2*3 is better
and we actually just end up with not borrowing at all!
so we can just *2 if we have an extra 2 > the result would be Math.pow(3, n/3)*2
Then, we have a couple corner cases two deal with since so far we only looked at
numbers that are larger than 3 > luckily, we only have 2 and 3 left,
which are pretty easy to figure out
Thus my final solution is
public class Solution {
public int integerBreak(int n) {
if(n <= 3) return n1; //assuming n >= 2
return n%3 == 0 ? (int)Math.pow(3, n/3) : n%3 == 1 ? (int)Math.pow(3, n/31)*4 : (int)Math.pow(3, n/3)*2;
}
}
Share some thought process about this problem


Okay, I will try to provide an informal proof of why we want as many
3s
as possible.Firstly, it is easy to see why the result is
n  1
forn < 4
. Therefore, we will only observe the casen >= 4
.The most optimal way to represent
4
is2 * 2
, again easy to see. What ifn > 4
?We claim that
3 * (n  3) > n
for alln >= 5
. This is indeed the case, since:3 * (n  3) > n 3n  9 > n  n 2n  9 > 0  +9 2n > 9  /2 n > 4.5 which is always true, since we assumed n >= 5.
With this proof we have actually shown that for any integer bigger than 4 it is actually better to decompose it as 3 times something instead of leaving it as it is.
Now we can recursively solve for
x = n  3
. The new cases are:1. x == 2  in this case we leave it as it is, which means that n % 3 == 2. This is covered by (int)Math.pow(3, n/3)*2 in his solution. 2. x == 3  corresponds to n % 3 == 0, which is covered by (int)Math.pow(3, n/3) 3. x == 4  corresponds to n % 3 == 1, which is covered by (int)Math.pow(3, n/31)*4, meaning that we multiply by 4 instead of 3 once. 4. x >= 5  in this case we can recursively solve for x.
A natural question would be why we chose exactly
3
and not any other number? It is indeed true that for any positive integerx >= 2
we havex * (n  x) >= n
forn
big enough. However, it wouldn't make sense to choosex >= 5
, as we have already proved that it is better to decompose it using as many3s
as possible. So the only candidates left arex = 2
andx = 4
:1. x == 4  We will have something like 4 * 4 * 4 ... * something. Let's take only the first two factors: 4 * 4 < 3 * 3 * 2, so we can substitute all of the fours with this expression, meaning that 3 is indeed the better choice. For the remaining nonthree factors, we can sum them up and use the same recursion. 2. x == 2  Similarly, 2 * 2 * 2 < 3 * 3.
The proof is not complete, but should be enough for you to understand the intuition.