This is the problem: You go to a shop and buy 4 items. The shop keeper tells you that it costs 7.11/- You ask him how he got it. He says that he multiplied the prices. You shout, “You are not supposed to multiply, but add the prices.” The shopkeeper laughs and says either way the price is the same. What are the prices of the items?

I could not solve this problem. Because at a glance, it occured to me that given the following information:

**a + b + c + d = 7.11**

**abcd = 7.11**

this problem cannot be solved analytically. But it never came to that with some tricks one can solve this problem programatically. That is the most revealing thing in this problem.

For brevity, lets multiply the prices by **100.** Then the sum becomes **711** and the product becomes **711,000,000**. One can bluntly keep three nested loops like this to solve it:

**m = 711000000;**

**for (a=1; a< 711; a++) {**

**for (b=1; b < 711-a; ; b++) {**

**for (c=1; c < 711-a-b;;c++) {**

**d = 711 – a – b – c;**

**if ((a*b*c*d) == m) return true;**

**} **

**}**

**} **

**return false;**

The very first optimization happens by observing the fact that any number that we select should divide **m**. So, we would not go into the next level of loop if the counter of the current loop cannot divide **m**.

### Like this:

Like Loading...

*Related*

vfasfd