Easy to understand C++ with explanation


  • 20

    For any integer p strictly greater than 4, it has the property such that 3 * (p - 3) > p, which means breaking it into two integers 3 and p - 3 makes the product larger while keeping the sum unchanged. If p - 3 is still greater than 4, we should break it again into 3 and p - 6, giving 3 * 3 * (p - 6), and so on, until we cannot break it (less than or equal to 4) anymore.

    For integer 4, breaking it into 2 * 2 or keeping it as 4 does not change its contribution to the product.
    We cannot have more than two 4s, because 2 * 3 * 3 > 4 * 4. We cannot have more than three 2s because 3 * 3 > 2 * 2 * 2.

    class Solution {
    public:
        long long integerBreak(long long n) {
            if(n == 2) return 1;
            if(n == 3) return 2;
            if(n == 4) return 4;
            if(n == 5) return 6;
            if(n == 6) return 9;
            return 3 * integerBreak(n - 3);
        }
    };

  • 0
    V

    Your solution seems to work like a charm , and I've seen similar solutions from this form as well. My question is : how do you come up with this idea of 'breaking integer into 3 and p-3 '? why not break it into 4 and p-4(when p>5) , 5 and p-5 and so on ? Thanks .


  • 1

    Thanks for commenting.
    Notice that we cannot have more than 2 consecutive 4s in the product, because 3 * 3 * 3 * 3 > 4 * 4 * 4. The same reason gives that we cannot have more than 2 consecutive 5s or 6, etc, because we can always replace it with 5 consecutive 3s, 6 consecutive 3s etc, and make the product larger:

    3 * 3 * 3 * 3 * 3 > 5 * 5 * 5
    3 * 3 * 3 * 3 * 3 * 3 > 6 * 6 * 6
    

    If we have 2 consecutive 4s, we should replace it with 2 * 3 * 3, because 2 * 3 * 3 > 4 * 4.


  • 0
    M

    @XBOX360555 grear explanation! thanks!


Log in to reply
 

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