This blog is for those people who like to solve algorithms and also for those who need some help in solving algorithms. Here we can post our problems, give solutions to the problems posted and also to discuss on the solutions like there complexities etc.
Sunday, June 20, 2010
[Microsoft] Puzzle: 12 balls problem
You have given 12 balls of identical shape and a weighing compares. There is one ball defective among them. How will you find out the defective one and whether it is light or heavy in less number of weighing.
step 1: Make 3 groups of four-four balls each. step 2: Compare any two of them. --> if they are equal: the defective ball is in third group --> else: the defective ball is in one of them.
Step 3: compare any one of them with the third group to find the group containing the defective ball and also by this way U'll get to know that the defective ball is heavy or light.
Step 4: From the defective group make subgroups of 2-2 balls and compare them to find one with the defective ball.
Step 5: Now by comparing the weights if these two balls U'll find the defective one.
step 1:
ReplyDeleteMake 3 groups of four-four balls each.
step 2: Compare any two of them.
--> if they are equal:
the defective ball is in third group
--> else:
the defective ball is in one of them.
Step 3: compare any one of them with the third group to find the group containing the defective ball and also by this way U'll get to know that the defective ball is heavy or light.
Step 4:
From the defective group make subgroups of 2-2 balls and compare them to find one with the defective ball.
Step 5: Now by comparing the weights if these two balls U'll find the defective one.
Here we are Comparing the balls only four times.