# O(log(n)) Time solution with explanation

• Given a number n lets say we have a possible product P = p1 * p2 * ... pk. Then we notice what would happen if we could break pi up into two more terms lets say one of the terms is 2 we would get the terms pi-2 and 2 so if 2(pi-2) > pi we would get a bigger product and this happens if pi > 4. since there is one other possible number less then 4 that is not 2 aka 3. Likewise for 3 if we instead breakup the one of the terms into pi-3 and 3 we would get a bigger product if 3*(pi-3) > pi which happens if pi > 4.5.

Hence we see that all of the terms in the product must be 2's and 3's. So we now just need to write n = a3 + b2 such that P = (3^a) * (2^b) is maximized. Hence we should favor more 3's then 2's in the product then 2's if possible.

So if n = a*3 then the answer will just be 3^a.

if n = a3 + 2 then the answer will be 2(3^a).

and if n = a3 + 22 then the answer will be 2 * 2 * 3^a

The above three cover all cases that n can be written as and the Math.pow() function takes O(log n) time to preform hence that is the running time.

``````public class Solution {
public int integerBreak(int n) {
if(n == 2)
return 1;
else if(n == 3)
return 2;
else if(n%3 == 0)
return (int)Math.pow(3, n/3);
else if(n%3 == 1)
return 2 * 2 * (int) Math.pow(3, (n - 4) / 3);
else
return 2 * (int) Math.pow(3, n/3);
}

}``````

• This post is deleted!

• Nice job! Thanks.
But the "a^3" in the following two lines should be "3^a":

So if n = a*3 then the answer will just be a^3.
if n = a3 + 2 then the answer will be 2a^3."

• Thanks for pointing that out.

• The same idea with you ,but use one line solution for the problem

``````class Solution {
public:
int integerBreak(int n) {
return n < 4 ? n - 1 : n%3 == 0 ? pow(3,n/3) : pow(3,n/3-1) * (2+2*(n%3));
}
};``````

• I wrote the similar code, but why we don't need to consider overflow, i tried when n=70, our solution is -4, but the expected answer is 2066242608. How to deal with this problem?

• Well you could always use long or Java BigInteger class to get a larger range.

• This post is deleted!