Given 1000 bottles of juice, one of them contains poison and tastes bitter. Spot the spoiled bottle in minimum sips.
We can do it in log(n) and that would be 10 sips. Of course it can be done in 1000 sips by checking each bottle but to do it in 10 sips you can take one drop from 500 bottles and mix them, if it is sour than the bottle is in those 500 or it is in different 500.Then out of those 500 you take 250 and do the same and rest is the binary search .
We can do it in log(n) and that would be 10 sips. Of course it can be done in 1000 sips by checking each bottle but to do it in 10 sips you can take one drop from 500 bottles and mix them, if it is sour than the bottle is in those 500 or it is in different 500.Then out of those 500 you take 250 and do the same and rest is the binary search .
No comments:
Post a Comment