A simple explanation of the math part and a O(n) solution


  • 116

    The first thing we should consider is : What is the max product if we break a number N into two factors?

    I use a function to express this product: f=x(N-x)

    When x=N/2, we get the maximum of this function.

    However, factors should be integers. Thus the maximum is (N/2)*(N/2) when N is even or (N-1)/2 *(N+1)/2 when N is odd.

    When the maximum of f is larger than N, we should do the break.

    (N/2)*(N/2)>=N, then N>=4

    (N-1)/2 *(N+1)/2>=N, then N>=5

    These two expressions mean that factors should be less than 4, otherwise we can do the break and get a better product. The factors in last result should be 1, 2 or 3. Obviously, 1 should be abandoned. Thus, the factors of the perfect product should be 2 or 3.

    The reason why we should use 3 as many as possible is

    For 6, 3 * 3>2 * 2 * 2. Thus, the optimal product should contain no more than three 2.

    Below is my accepted, O(N) solution.

    public class Solution {
        public int integerBreak(int n) {
            if(n==2) return 1;
            if(n==3) return 2;
            int product = 1;
            while(n>4){
                product*=3;
                n-=3;
            }
            product*=n;
            
            return product;
        }
    }

  • 0
    D

    4 * 4 is not the maximum when N is 8

    "Thus the maximum is (N/2)*(N/2) when N is even"


  • 4
    D

    I think a simpler math explanation is to say,

    "Prove that for all integers n > 4, ( ( n-3 ) * 3 ) > n".

    This gives reason to the 3, and why we may want to consider special cases for preceding numbers. Maybe not simpler, but a stronger explanation in my mind.


  • 2
    E

    The optimal product should contain no more than two 2

    I think a good way to explain why we need to use 3 as much as possible is: assume a breakdown has 3 twos, those 3 twos have a product of 8 which is less than the product of 2 threes(we can improve it that way). So we can prove the breakdown can have at most 2 twos. Thus, the conclusion is we should use 3 as much as possible.


  • 0
    This post is deleted!

  • 3

    Comment to DaHa Song: This is to say that if you want to break once, breaking in this way can give you the maximum. However, we need to do the break several times to get the optimal product. If you always do the break as (N/2)*(N/2), it is a greedy algorithm, and as we know, greedy is not always the optimal.


  • 0
    P

    "(N-1)/2 *(N+1)/2, then N>=5" should be "(N-1)/2 *(N+1)/2 >=N then N>=5" isn't it? the resulting equation woud be N^2-4N-1>=0 which has roots N>=4.23 and N<=-0.23, because N is integer, then N must be N>=5


  • 0
    S
    This post is deleted!

  • 0
    S

    Well, a very nice explanation. But I think there is a little flaw in your derivation.

    "When the maximum of f is larger than N, we should do the break."

    Here, we should use ">" instead of ">=". Thus, it's OK when N is odd, but the solution should be "N > 4" when N is even. Following that change, we get different effective factors, which are 2 and 4. We have to take factor 4 into consideration.

    The reason why your solution happens to be correct is the fact that 4 = 2 + 2 and 4 = 2 * 2. Based on my derivation, we should think of a reason why we use as many as 3 while not 4.

    Here it is. We can consider addition.

    First got the situation of equation:
    For 7, 3 * 4 = 4 * 3, also 4 + 4 + 4 = 3 + 3 + 3 + 3
    For 5, 2 * 3 = 3 * 2, also 3 + 3 = 2 + 2 + 2

    Then we consider the inequality:
    For 8, 4 * 4 < 3 * 3 * 2
    For 6, 2 * 4 < 3 * 3 and 2 * 2 * 2 < 3 * 3
    For 9, 10, 11, ...

    I know that's not strict. But heuristically, that's why we choose as many as product of continual 3s rather than other combinations of 2s or 4s.

    Following my derivation, the loop looks like "while(n > 4)". But through @Chuqi's derivation, that doesn't make sense.


  • 0
    L

    Awesome !

    The core ideas of this problem are

    1. all factors should be 2 or 3 (N > 4)
    2. 3 * 3 > 2 * 2 * 2.

  • 0

    super clear explanation! thank you !


  • 0
    S

    brilliant solution & explanation


  • 0
    V

    You are pretty clever!


  • 0

    Hello, why while(n>4) could not equal to 4, I mean while(n>=4)


  • 1
    A

    @wxl163530 I think you could take 7 as an example. If n>4, the product would be 34 =12, but if it is n>=4, it would 33*1 = 9.

    Because it has been proved before (N/2)(N/2)>=N, then N>=4, based on this, if you wanna break 4, it should be 22 instead of 31. Moreover, even if you don't break 4 continually, 4 is the same as the product of its factors 22. So you don't need to break it to 3*1.

    Just my thoughts.


  • 0

    @ainiyouyou
    I see~ , thanks for replying.


Log in to reply
 

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