PROGRAMMING INTERVIEWS

Also note that the rate of consumption remains constant no matter how we subdivide the distance, as long as the number of trips required is the same.

So we have seen that if we have (Cn + y) where n is an integer and 0<y<=C at any point in time, our cost of walking each km is (2n+1). And from next transit point this rate will become (2n-1). We need to choose transit points such that we reduce one round time every time. In this manner, transit point will come when remaining bananas are integer multiple of C. Now you have a subset of bananas and distance left. You can apply the same process on remaining values.

This recursion will converge, when remaining bananas are less then or equal to C. (So that we can transfer all of them in single trip.)

double transferBananas(double N, double D, double C, double F) {
// base case: remaining bananas <= C,
// so carry all the bananas in one trip
// at this point if distance is more than N/F,
// elephant can never reach destination, return 0
if (N <= C) {
 double bananasAtDestination = N - D*F;
 return (bananasAtDestination >= 0.0) ?
         bananasAtDestination :  0.0;    // out of bananas!
}

// # trips you would travel back and forth
int numTrips = 2*(ceil(N/C) - 1) + 1;

// how many bananas you consume per km
double costPerKm = numTrips * F;

// remaining number of bananas after consumption, we want it
// as an integer multiple of C.
double remainingBananas = C*(ceil(N/C) - 1.0);

// this is the distance you are able to travel before you
// reach ONE LESS round trip fetching bananas
// derived from eq: N - costPerKm * traveled = remaining bananas

double traveled = (N - remainingBananas) / costPerKm;

// we are able to travel greater (or equal) than the remaining
// distance, so fetch the bananas right to the destination
if (traveled >= D)
 return N - D*costPerKm;

// calculate recursively as we travel ONE less round trip now.
return transferBananas(remainingBananas, D-traveled, C, F);
}

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.