Q. Given a number n, find a set such that –

- Sum of all the elements should result into n.
- Multiplication of all the elements should be greater than any other similar set (whose elements result n when summed up).

A. This is a very interesting problem as we have to go through every combination and calculate and compare the multiplication. Since, there is no restriction on the length of the subset, it makes problem much more interesting.

I propose use of dynamic programming here. We will start computing the f(n) from 1

At every stage, we have to compute all combinations of f(1).. f(n-1)

f(n) = max {

f(1) * f(n-1)

f(2) * f(n-2)

….. }

To avoid repeated operations, we can store start computing f(1).. f(n-1) one by one and do the book keeping of the result.

### Like this:

Like Loading...

*Related*

I believe we dont have to calculate for all combination. This is because if we want to split a number into two, such that their sum is the number and product is maximum, then it should be divided as:

first= n/2;

second =n-first;

eg: n=45; first= 22, second =23;

Now recursively, we can apply the same logic on ‘first’ and ‘two’. Pseudo-pseudo code follows:

int[] getBestBreakup(n){

if(n<=4){

return make_array(n);

}

first =n/2;

second=n-first;

array= join_array( getBestBreakup(first), getBestBreakup(second));

return array;

}

// make_array(n) means an array containing only n

// join_array means combine the two arrays into one;

Please comment 🙂

Thanks

Well, that doesn’t always work 😀

let me put up an example:

base number : 9

From your algorithm, we’ll break it up in

4,5

then further into

2,2,2,3

Multiplication turns out to be 24

But, the best case here is 3,3,3 = 27

The solution I suggested is more algorithmic. If we follow mathematics, we should be looking for closest of squares/cubes as they rate with highest multiplying factor.

Anyway, this had to be done for each level, not sure if we would be saving time by exponential factor.