We all love algorithms. In real life, the problems do not pose themselves as textbooks problems under a particular chapter so that we know what algorithm to apply. The problems are camouflaged. The challenge lies not in implementing the algorithms but identifying the problem in its abstract form and finding out the appropriate algorithm to apply.

I have had a few chances at my work where I’ve had this Aha! feeling along with my colleagues where we talked about the problem, reformulated it and then discovered that the problem is a likely candidate for applying some algorithm X. This is the first part of this series.

To boost the sales of our product, we had come up with certain promotions. Some were simple flat rate discount, some were % discounts. Then we embarked on this idea of buy-one-and-get-one-free. Here the user chooses products of different prices and pays for approximately half the price. It is similar to buy-one-shirt-and-get-one-free (where you pay for the costlier one). Just that here it is bundle of products.

Let me explain with an example.

1. Suppose a customer buys products each worth $10, $30 & $100. Then the customer would pay $100 and get $40 (=10 +30) worth products free. So this ain’t a simple buy-one-get-one free.

2. If customer buys two products each worth $100, then she pays $100 and gets the other one free.

3. If the purchases are $10, $100, $45, $40, $10 then customer pays $105 (= 10+45+40+10) and gets the $00 product free.

This should give a fair idea of what we want to achieve. A little thought would suggest such a reformulation of the problem above.

*“Given a set of numbers, split it into two parts such that the difference between their sums is the least.”*

This is quite straight forward to solve. The plan is given below.

1. sort the numbers in **descending** order.

2. have two buckets call them L & R.

3. put the first one into L (l1). put the second one into R (r1).

4. take the third one x3.

if r1+x3 > l1 then put x3 in L1

else put x3 in L2

Now it is a matter of policy whether the customer is charged the higher one or the lower (in cases where the split is unequal)

If you like this you might probably like this as well.

### Like this:

Like Loading...

*Related*

Dante

said:Yeah you are right if the array of numbers is streaming from some source.But actually we have got a fixed array of numbers. we are going to divide this array into 2 arrays of least difference in their sums.To put in other words we are going to divide this array into 2 arrays such that the sum of each array is close to the (sum of the original array /2).So the algorithm would be o(n) instead of o(nlogn) as in your case.

t-total sum of original array

s-0

for each element in array

{

if((s+element)<t/2)

{

s=s+element

put element in L array

}

else

put element in R array

}

Correct me if I am wrong ….

Intensity !

said:Hi Dante

Thanks for your pointers. Your approach is quite simple and elegant.

I guess in my approach, the precondition that the array be sorted is of significance. Even if the source is streaming, the numbers should arrive in the sorted (descending) order.

If the incoming numbers are inserted into a priority queue, and then read back from it, the output would be in the descending order of the numbers.

The complexity for insert and remove for Priority queue is N log N, which is what you have pointed out.

In the context where I used this, the numbers were already in the sorted order and dint incur the N Log N expense. But in the generic case, I would do as you have suggested.

Pingback: algorithms @ work - part 2 « null pointers …

Xtrasize Male Enhancement

said:You should be a part of a contest for one of the most useful

blogs on the net. I most certainly will recommend this site!

http://getridofherpesnow.net

said:It is appropriate time to make some plans for the future and it is time to be happy.

I’ve read this post and if I could I wish to suggest you some interesting things or suggestions. Maybe you could write next articles referring to this article. I desire to read more things about it!

no2 maximus reviews

said:Hello there! I just want to offer you a huge thumbs up for the excellent information

you’ve got right here on this post. I will be returning to your web site for more soon.

Oxitamin

said:Hi there i am kavin, its my first occasion to commenting anywhere,

when i read this article i thought i could also create comment due to this brilliant paragraph.