# All your solution is wrong

the 2142770112 is product of [2, 3, 7, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3].
too simple too naive, when the input is larger than 60,the problem is dramatically changed.
this is my accepted code ,so I think the problem is partly wrong.

``````public int integerBreak(int n) {
int m = (int) (Math.log10(Integer.MAX_VALUE) / Math.log10(3));
if (n < 2)
return 1;
if (n <= 7)
return n / 2 * (n - n / 2);
if (n <= 3 * m + 1) {
if (n % 3 == 0)
return (int) Math.pow(3, n / 3);
if (n % 3 == 1)
return (int) Math.pow(3, n / 3 - 1) * 4;
if (n % 3 == 2)
return (int) Math.pow(3, n / 3) * 2;
}
if (n > 3 * m + 1) {

}
return 0;
}
``````

• How did you get the answer? Could you post some code?

• Agreed.
I was myself stumped when I discovered that `max product` can be dramatically large.
Take the case of `n = 90`.

Break it as `[ 2, 2, 2, ...... , 2, 2, 2 ]` and you get a product of `35184372088832`

Break it as `[ 3, 3, 3, ...... , 3, 3, 3 ]` and you get a product of `205891132094649`

And expected answer is: `2124471432`

• 61 breaks into
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2]
in my code, whose product is
4649045868.

My theory is this:
For positive ints who are bigger than 4, the product always increases(except for powers of 2 and three) when the number is broken down into two n/2, since n^2 / 4 is always bigger than n when n > 4. Then we have choices of breaking numbers into [1,2,3,4]. Here, since 4 = 2*2, 4 can be dropped, and 1 is meaningless, it can be dropped do. So number should always break into sum of [2,3], and it is easy to know that it is always beneficial to prefer 3 to 2. In conclusion, break your number into 2 and 3 (if number is bigger than 3), and have at most two 2's.

Here's my naïve code.

``````def integer_break(n)
return 1 if n == 2
return 2 if n == 3
raw_parts = [n]
processed_parts = []
while raw_parts.any?
part = raw_parts[0]
if part -3 > 1
raw_parts[0] -= 3
processed_parts << 3
elsif part -2 > 1
raw_parts[0] -= 2
processed_parts << 2
end
if raw_parts[0] <4
processed_parts << raw_parts.shift
end
end
puts(processed_parts.to_s)
processed_parts.reduce(1) {|x,y| x*y}
end``````

• 7 as a factor? How could it be larger than 3*3*1 or 2*2*3?

• @tototo I don't quite understand.. @jxyzmahuan has given the example with 7. Remember the sum has to be equal to 61 in his example.
Although that is not the optimal solution and IMO neither is the `'expected answer'`.
If you break `61` as `[ 2, 2, 3, 3, 3, ...., 3, 3 ]` you get a `product of 4649045868`.
Also, check the example of `n = 90` in my previous comment.

• @tototo I know the factor must be 2 or 3 ,but if the test case larger than 61 then overflow. I think we must find the largest number not over flow.

• @cjeon I know the factor must be 2 or 3 ,but if the test case larger than 61 then overflow. I think we must find the largest number not over flow.

• @tototo know the factor must be 2 or 3 ,but if the test case larger than 61 then overflow. I think we must find the largest number not over flow.

• @mishrasonu1993 my code is

public int integerBreak(int n) {
int m = (int) (Math.log10(Integer.MAX_VALUE) / Math.log10(3));
if (n < 2)
return 1;
if (n <= 7)
return n / 2 * (n - n / 2);
if (n <= 3 * m + 1) {
if (n % 3 == 0)
return (int) Math.pow(3, n / 3);
if (n % 3 == 1)
return (int) Math.pow(3, n / 3 - 1) * 4;
if (n % 3 == 2)
return (int) Math.pow(3, n / 3) * 2;
}
if (n > 3 * m + 1) {

``````	}
return 0;
}``````

• This was apparently not intended and the note has just been extended to say "You may assume that n is not less than 2 and not larger than 58."

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