Find the Best Multiplying Breakup of a Number

Posted: February 13, 2011 in Algorithms, CA, data structures

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.

Advertisements
Comments
  1. aqs says:

    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

  2. Harsh says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s