suppose there are n balls. out of which only one ball is lighter in weight. you are given a simple balance. then how many minimum no. of attempts do you take to find out that lighter ball. and how many maximum numbers of attempts do you seek to find out the lighter ball? he also added that to find a maximum number of attempts there is a certain condition and he asked me to find that
Answers
Answered by
1
This is a divide and conquer problem.
Put n/2 balls on both sides of balance. remove the side which is heavier.
then again split those n/2 balls and but them in both sides of balance (n/4 one side and n/4 on the other)
Continue doing it till you are left with 1 ball in each side of balance, you will find the lighter one.
Maximum attempts in floor(log2 (n))
Similar questions