@tanveer-malhotra this might need some explanation. (this is commonly called as camel and banana puzzle and is a frequent visitor in interviews for programming roles!)3000 km from Source to Destination. Elephant need 1 banana per km and it can carry at max 1000 banana at a time. If elephant try to go straight to destination it will eat all the 1000 bananas in 1 km itself). So we need to find an intermediate position where we can store the bananas on the way. So the elephant should shuttle between source and intermediate and this brings in one more constraint that the intermediate should never be more than 500 km away from the source. Else, elephant won't have any banana left to return to source.
Source ---------------------------- Intermediate ------------------------- Destination
With 3000 bananas in total, elephant can make 3 trips from source. So it would be liketake 1000 bananas from source ---> travel to intermediate ---> store all the bananas at intermediate after taking enough bananas for return travel --> travel to source --> repeat (3 times)So we can see the path between source --- intermediate is covered 5 times here. Now comes the key part. This stretch of Source -- Intermediate cost us 5 banana per km. So we need to ensure the intermediate is located at a place where the elephant can store max of 2000 bananas. Why ? Because after that, 2000 bananas can be transported to destination (or another intermediate) at a cost of 3 bananas per km (explained below) which is better than spending 5 bananas per km.(adsbygoogle = window.adsbygoogle || []).push({});
Source ---------------------------- Intermediate1 -------------------- Intermediate 2 ------------------------- Destination
take 1000 bananas from intermediate 1 ---> travel to intermediate 2 ---> store all the bananas at intermediate 2 after taking enough bananas for return travel --> travel to intermediate --> repeat (2 times)
So here we can see the stretch intermediate 1 --- intermediate 2 is covered at a cost of 3 banana per km.
So we have to be left with 2000 bananas at intermediate 1. As we are spending 5 bananas per km in this stretch, we can say 5d = 1000 ==> d = 200. So Intermediate 1 is 200 km away from source.
similarly we should ensure we bring 1000 bananas to intermediate 2, (as then the elephant can just take them all to destination in one shot - spending 1 banana per km)
So 3d = 1000 => d = 333
So intermediate 2 is 333 km away from intermediate 1.
Distance left till destination from intermediate 2 = 1000 - (200 + 333) = 467
If elephant takes 1000 bananas from intermediate 2, there will be 1000 - 467 = 533 bananas transported to destination.
Here if you see, what we did is to optimize the price per km (in banana units!) and ensure we place the intermediate points such that it would be a multiple of the maximum carrying capacity. Like source (3000 bananas), Intermediate 1 (2000 bananas) and intermediate 2 (1000 bananas)..(adsbygoogle = window.adsbygoogle || []).push({});
Got it ?
That was lot of typing... Phew!!!