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

• ``````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.

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