A merchant has bough some 3000 banana from market and want to bring them to his home which is 1000 km far from Market. He have a elephant which can carry maximum of 1000/- banana at time. That could have been easy but this elephant is very shrewd and he charges 1 banana for every one kilometer he travel. Now we have to maximise number of banana which should reach to home. Solution: At present we are at 0th km with 3000 banana and elephant. Lets see if elephant have to shift all the 3000 banana and elephant by 1 km. For 1 km shift: Take first 1000 banana and drop at 1st km. 2 banana consumed. One banana each for to and fro. Second 1000 banana and drop at 1st km. 2 banana consumed. Third 1000 banana and reach at 1st km. 1 banana consumed. So all in all total 5 banana will be consumed if we shift a kilometer. But that's not all, our total banana number are also reducing so we may have to reduce the number of turns too. And this will happen once we have reduced the b
is there any constraint on TC? if not following is quadratic
ReplyDeletestart with 2 pointers,
p1: beginning of array
p2: at the middle(beginning of the second half)
compare the two,
while(p1 is does not reach middle)
if(*p2<*p1)
{
rotate the array from p1 to p2
incr p1 nad p2
}
else
incr p1
// if equal then you can incr either p1 or p2
nlogn mein to aise hi ho jayega yar
ReplyDeletey doin it in quadrtc