C++ Pure Math O(1) Space O(logN) Time


  • 0
    F

    I find the mathematical solution first then came up with this solution to handle integer only.
    Mathematically, the optimal base amount is actually e=2.71828.
    In other words, given N, e^(N/e) is the maximal product you can get by breaking N into N/e numbers;
    To handle integer, just need to do some special handling.

    class Solution {
        int n;
        int solve(int k)
        {
            if (k < 2)
                return 0;
            int a = n/k;
            int m = n - a * k;
            return pow(a+1, m) * pow(a, k - m);
        }
    public:
        int integerBreak(int i) {
            n = i;
            int k = max(n/2.718281828459, 2.0);
            return max(solve(k - 1), max(solve(k + 1), solve(k)));
            
        }
    };

  • 0
    G

    Can you please explain how you approached this problem ?
    What made you look at "e" ?
    I'm really curious as to your though process.
    Thank you.


  • 0
    F

    It is a typical math problem:
    Given ab = N, find the maximal value of a^b. This can be solved using basic calculus, and the answer is when a = e, b = N/e, a^b reaches max value;


Log in to reply
 

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