C++ O(N) Mathematical approach


  • 0
    B

    7 = 2+2+3

    8 = 2+3+3

    9 = 3+3+3

    10 = 3+3+4

    we can see that when numbers on the right are as close as possible,their product is the largest.

    class Solution {
    public:
        int integerBreak(int n) {
            if (n <= 1) {
                return 0;
            }
            int result = 0;
            int positive;
            int num_larger = 0;
            for (int num = 2; num <= n; num++) {
                positive = n / num;
                if (n % num == 0) {
                    result = max(result, (int)pow(positive, num));
                }
                else {
                    num_larger = n - num * positive;
                    result = max(result, (int)pow(positive, num - num_larger) * (int)pow(positive + 1, num_larger));
                }
            }
            return result;
        }
    };

Log in to reply
 

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