• ``````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/3-1)*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 n-1; //assuming n >= 2
return n%3 == 0 ? (int)Math.pow(3, n/3) : n%3 == 1 ? (int)Math.pow(3, n/3-1)*4 : (int)Math.pow(3, n/3)*2;
}
}``````

• I just want to know why when should break it into 3s as more as we can ?
is there any theorem or how to prove it?

• 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` for `n < 4`. Therefore, we will only observe the case `n >= 4`.

The most optimal way to represent `4` is `2 * 2`, again easy to see. What if `n > 4`?

We claim that `3 * (n - 3) > n` for all `n >= 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/3-1)*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 integer `x >= 2` we have `x * (n - x) >= n` for `n` big enough. However, it wouldn't make sense to choose `x >= 5`, as we have already proved that it is better to decompose it using as many `3s` as possible. So the only candidates left are `x = 2` and `x = 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 non-three 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.

• this is really clever. thank you for sharing

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