Break a positive integer into the sum of at least two positive integers and return the maximum product

Question

So this is a recent interview question, Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

I'm trying to solve it recursively, The approach is first split the number into two halves and find the max product and keep splitting each half till we get the maximum.

This is my code,

private int integerBreak(int n, int maxProduct){

        int index = 0;
        for(int i=0; i<n; i++){
            if((i * (n-i)) >maxProduct) {
                maxProduct = i*(n-i);
                index = i;
            }
        }
        return integerBreak(index, index) * integerBreak(n - index, n-index);
    }
    public int integerBreak(int n) {

        int maxProduct = 0;
        return integerBreak(n, maxProduct);

    }

Now I'm a little lost with the base condition as to how to terminate recursion. I'd appreciate if someone can help me with my approach rather than coming up with the completely different solution.

Answer 1

As I wrote in the comment above, we have to break the number into 3s. If we derive the maxima, we get the e (base of the logarithm) to be 2 < e < 3. But the thing is 6= 33 and 6=22*2 so every triplet of 2 can be replaced with a tuple of 3 for the maximum product.

So here is the code I wrote. It is in Python so I hope you don't mind -

def maximize_product(num):
product = 1

if num == 2 or num == 3:
    return num - 1

else:
    while num > 4:
        product = product * 3
        num -= 3

return num * product

Answer 2

The idea is to break the number into multiples of 2 or 3. If you write the breaking results for couple of numbers like 7 to 10 you should get the idea. Assuming the max number is 60, there is a simple dynamic solution:

int dp[60];
public:
int integerBreak(int n)
{
  dp[1]=1,dp[2]=1,dp[3]=2,dp[4]=4,dp[5]=6,dp[6]=9;
  for(int i=7;i<=n;i++)
     dp[i]=max(dp[i-3]*3,dp[i-2]*2);
  return dp[n];
}

};

Answer 3

Here's my solution to the problem : (Idea : It is optimal to break integer into multiple of 3)

public int integerBreak(int n) {

    // base case : 
    if (n == 2 || n == 3){ 
       return (n-1);
    }

    int maxProduct = 1;
    while (n > 4){
        n -= 3;
        maxProduct *= 3; // Keep multiplying 3.
    }
    return (n * maxProduct); // multiply with left over n.

}

This is simple O(N) solution. Hope this helps someone !

Answer 4

I wrote a straightforward Java application to calculate the maximum product for the sum of integers of the numbers 2 through 20. The first number is the sum. The middle numbers are the factors of the sum. The final number is the product of the factors. Here are the results.

2   [1, 1]   1
3   [2, 1]   2
4   [2, 2]   4
5   [3, 2]   6
6   [3, 3]   9
7   [4, 3]   12
8   [3, 3, 2]   18
9   [3, 3, 3]   27
10   [4, 3, 3]   36
11   [3, 3, 3, 2]   54
12   [3, 3, 3, 3]   81
13   [4, 3, 3, 3]   108
14   [3, 3, 3, 3, 2]   162
15   [3, 3, 3, 3, 3]   243
16   [4, 3, 3, 3, 3]   324
17   [3, 3, 3, 3, 3, 2]   486
18   [3, 3, 3, 3, 3, 3]   729
19   [4, 3, 3, 3, 3, 3]   972
20   [3, 3, 3, 3, 3, 3, 2]   1458

The calculateMaximumFactors method calculates the factors with the maximum product. The factor method generates the factors of the sum. The product method calculates the product of the factors. Here's the code:

package com.ggl.testing;

import java.util.Arrays;

public class MaximumProduct {

    public static void main(String[] args) {
        for (int sum = 2; sum <= 20; sum++) {
            System.out.print(sum + "   ");
            System.out.println(calculateMaximumFactors(sum));
        }
    }

    private static String calculateMaximumFactors(int sum) {
        int[] previousFactors = new int[0];
        int maxProduct = 0;

        for (int i = 2; i <= sum; i++) {
            int[] factors = factor(sum, i);
            int product = product(factors);
            if (product > maxProduct) {
                maxProduct = product;
                previousFactors = Arrays.copyOf(factors, factors.length);
            }
        }

        return Arrays.toString(previousFactors) + "   " + maxProduct;
    }

    private static int[] factor(int sum, int divisor) {
        if (sum < divisor) {
            return new int[0];
        }

        int num = sum / divisor;
        int remainder = sum % divisor;
        int[] result = new int[divisor];
        for (int i = 0; i < divisor; i++) {
            result[i] = num;
            if (remainder > 0) {
                result[i]++;
                remainder--;
            }
        }

        return result;
    }

    private static int product(int[] factors) {
        int product = 1;

        for (int i = 0; i < factors.length; i++) {
            product *= factors[i];
        }

        return product;
    }

}

Answer 5

If you make a loop trying to find the number then is going to get complicated and not as efficient (the greater the number, the longest will take you to find it, you need to consider indexes, etc etc)

The best and fastest algorithm is the middle point algorithm, i.e divide the given number by 2, calculate deviation if number is odd, finally calculate the product

Example:

static int func(int number) {
        int result = 0;
        if (number < 0) {
            System.err.println("no negative allowed");
            System.exit(0);
        }
        int a = 0;
        int b = 0;
        a = number / 2;
        b = number / 2;
        a += number - (a + b);
        result = a * b;
        System.out.println(" this is a " + a);
        System.out.println(" this is b " + b);
        return result;
    }

if you execute it like

public static void main(String[] args) {
    int number = 9;
    int result = func(number);
    System.out.println(result);
}

will get the results correctly...