I hope this is the most intuitive way to express the math behind this problem


  • 1
    F
    class Solution {
    public:
        int integerBreak(int n, bool first_split = true) {
            // p = x[0] * x[1] * ... * x[i] * ... * x[n]
            // For any x[i]:
            //     Hint1: 1 * (x[i] - 1) >= x[i] => impossible
            //     Hint2: 2 * (x[i] - 2) >= x[i] => if x[i] >= 4
            //     Hint3: 3 * (x[i] - 3) >= x[i] => if x[i] >= 4.5
            //         =>
            //             Hint4: 4 * (x[i] - 4) <= 2 * 2 * (x[i] - 4)
            //             Hint5: 5 * (x[i] - 5) <= 2 * 3 * (x[i] - 5)
            //             Hint6: 6 * (x[i] - 6) <= 2*2*2*(x[i] - 6) <= 3*3*(x[i] - 6)
            //             ...
            // Conclusion1: we can split x[i] into 2s and 3s
            // Conclusion2: From Hint3, Hint5 and Hint6, 3s are prefered if x[i] > 4
    
            if (!first_split && n <= 4) {
                return n;
            } else if (n == 1 || n == 2) {
                return 1;
            } else if (n == 3) {
                return 2;
            } else if (n == 4) {
                return 4;
            } else {
                return 3 * this->integerBreak(n - 3, false); // This line can be optimized
            }   
        }   
    };
    

    Mathmatical induction.


Log in to reply
 

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