O(n) Java solution based on inequality of arithmetic and geometric means

  • 0

    I assume you heard about the inequality of arithmetic and geometric means (in case you are not, here is a Wiki link). Basically what it says is that for a group of non-negative numbers x1, x2, ..., xk, their geometric means is always less than or equal to their arithmetic means, or mathematically,

    (x1 * x2 * ... * xk) ^ 1/k <= (x1 + x2 + ... + xk) / k.

    and the condition for the equality is that all numbers are equal: x1 = x2 = ... = xk.

    Now for our problem, given a positive integer n, we have at most (n - 1) ways to break it into a group of positive integers(at least two numbers): a group of two integers, a group of three integers, a group of four integers, ..., a group of n integers. For each group of integers, we can apply the inequality above and find the maximum of the geometric means (which implies maximum product of the integers for that group). We then choose the group that yields the maximum product as our answer.

    The only tricky part is that the condition for equality may not be met, since now we are dealing with integers.
    For a group of k numbers, n is not necessary a multiple of k, therefore we cannot have k equal numbers for this group. In this case, it is assumed that the closer all the integers in the group are, the larger the geometric means will be, i.e., we need to make the integers in the group as close to each other as possible.

    Here is the method taken to accomplish that purpose: for a group of k integers, let p = [n/k], q = n % k (here p is the integer part of n/k). We then distribute q evenly among the k integers such that q out k numbers will have value (p+1) while the rest have value p. And the geometric product will be (p+1)^q * p^(k-q). If we assume the power function takes O(1) time, then the algorithm will run in O(n) time. Here is the Java program:

    public int integerBreak(int n) {
        double max = 1;
        for (int i = 2; i <= n; i++) {
            max = Math.max(max, Math.pow(n / i + 1, n % i) * Math.pow(n / i, i - n % i));
        return (int)max;

Log in to reply

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