GIven 9 balls all of which weigh the same except for one, what is the minimum of weighings necessary to find the ball weighs more (or less).

I agree with Anonymous in that these questions don't tell much about character. However, I can't beleive nobody here is analytical enough to come up with the correct answer. First off, the question is not stated correctly. The scale should be a simple balance, and the objective is to find the "odd" ball AND determine if it is heavy or light. The answer is three. First separate into three groups of three, G1, G2, and G3. In the first two weighings you can determine which group has the "odd" ball AND if the odd ball is heavy or light. Weighing 1 - weigh G1 against G2: Two outcomes 1) G1 == G2 --> Odd ball is in G3, in Weighnig 2, use either G1 or G2 against G3 to determine if Oddball is H or L 2) G1 != G2 -> Odd ball is NOT in G3 but you now know if G1 is heavier or lighter than G2, in Weghing 2, use either G1 or G2 against G3, for instance use G2 and G3, if same, then G1 has oddball and you know if its H or L, if G2 != G3, then G2 has odd ball and you know if it is H or L Now that you know which G it is in And the disposition of the Oddball (Heavy or Light), weigh any two of the Group containing the oddball, and based on your knowledge of wether the oddball is H or L, you know which one it is and its disposition. Any offers??

You could do this with two weighings assuming its a two pan balance - (1) place three balls on each side - if they balance out then its the remaining three that has abnormal ball (2) out of that group, place one ball on each side - if balances it out, the abnormal ball is the remaining one. If the weighing in step (1) does not balance out, grab the group of three balls that is light or heavy and repeat step (2) described above.

While the solution above is correct, more or less, you first should clarify the question and spell out any assumptions. The assumption here is that you know or are aware beforehand that only one ball is of different weight. Sometimes your ability to clarify and state assumptions is more valuable than getting the right answer. Sometimes you can arrive at the right answer with the wrong logic which helps you solve this problem, but may mess you up in the future.

Suncoastgal has a point, and most of the answers above are simplifying this problem a bit. You are not told if the odd ball is heaver or lighter, which complicates things. The most efficient method is that described by 'questions like this...' as method 2. Split balls into 3 groups and weigh two. The worst outcome is if the groups do not weigh the same, so assume that happens. All you know now is that the odd ball is NOT in the reserved group of 3, so set those aside. You don't know which of the two weighed groups contains the odd ball, so now you have 6. Repeat the first step with groups of 2 balls. Again the worst outcome is that the scales don't balance, so you've eliminated 2 more balls and only know that the odd ball is one of 4. As near as I can tell, you still need 2 more steps now to guarantee finding the odd ball: Choose any two balls from the 4 and compare. If they are the same, the odd ball is in the reserved 2, if they differ the odd ball is one of the two you weighed. Now take one of the two balls that might be odd, and weigh against one of the balls you have been setting aside as 'normal'. By the way, although you now know which ball is odd, you may still not know if it's heavier or lighter. If the last weighing balances, you only know that the other ball is odd, and you would have to weigh it against one of the 'normal' balls to see how it is off. You can do this problem in only 2 weighings if you are told whether the odd ball is heavy or light before you begin.

In lieu of the fact that we don't know whether the ball is heavier or lighter then the rest, you would have to do 3 weighings. 1: ooo/\ooo ooo Do the first weighing as pictured above to isolate the set of balls that you know for a fact weigh the same. Then, in the second weighing, use that set to isolate the set that contains the odd ball. The second weighing should also tell you whether the odd ball is heavier or lighter because of how the scale reacts when you replace the control set with the unknown set. If the scale stays tipped down to the side opposite the control set, then it's heavier. If it stays tipped up, then it's lighter. If the scale was balanced before the second weighing, then you know that the remaining set is the set that has the odd ball, and replacing it with a set that you know all weigh the same should still tell you whether the ball is heavier or lighter by watching how the scale behaves. Then you can proceed to the 3rd weighing to isolate the heavier/lighter ball. So my mistake everyone -- the correct answer is 3 weighings when you don't know if the ball is heavier or lighter.

Keep it simple. If it's 3-state balance you need log2(9) / log2(3) attempts since you can encode 9 states using 2 3-bit states.

The question is perfect to define how the person takes directions - how many assumptions the person does before start the job - how many questions the person asks (if asks) to make clarifications before start the job. Also, I see there another result - all answers come finally to two groups of getting result : 1) to get faster the first result but more steps for guaranteed result - from 1 to 4 steps or 1 to 4 weightings for combination 4+4+1 2) to get faster guaranteed result - from 2 to 3 steps for starting combination 3+3+3, I would say that BMF scheme contains one additional step (comparison of weight lighter/heavier - definition what of them is consider to be "odd" ), which in solution structure should be equal to the additional step, so it comes to from 2 to 4 steps but still in 2 to 3 weightings. After all, I would say that you may get from this question: How the person understand the task How many assumptions the person does before start the job How many questions the person asks before start the job How many solutions and ideas the persons generates. How the person make a choice to present one solution from multiple (say fastest first result vs fastest guaranteed result). Etc.

The candidate should clarify if they truly mean the minimum to find the odd-weighted once, or everytime. I agree that it only takes one weighing (and some luck) to find it. Actually, the person could randomly guess (not weigh any) and get the right ball. So you need to understand the balance of risk vs. cost. By the way, simple logic problems do trip up people that you don't want working for you (depending on the job). So I like the question.

It is interesting to speculate if the question wording is being cute or tricky by saying "more (or less)". Is it just being general and saying find the odd ball, or is it being tricky and saying find the odd ball AND tell me if it is lighter or heavier. I think it is being over thought here and just means find the odd. In that case the answers saying 2 weighings is the best you can guarantee. None of this lucky crap. BMF had it if you had to determine if it was in fact heavier or lighter instead of being told. So if the question had the added clause that if you really tried it and didn't get it in the number of tries you answered (or fewer), then you would be killed, would you still say "just one if you get lucky"?

These type of interview questions are so lame. They don't sniff out the lazy people, the coders who write crap no one can decipher, and can't or won't write maintainable code. Yes you want people who can problem solve and break down problems into manageable chunks, but how often do software projects fail? Answer = 70-90% and that's mostly due to poor management, not giving clients what they want, feature creep, poor quality, etc. So how is answering this question going to tell me that this new hire has integrity and can throw out his ego and write code for a real life product that people want to use? No wonder so much software is trash. (And yes I've been programming for 25 years and see the same errors happening over and over, it's pathetic and completely fixable.)

Suncoastgal has a point, and most of the answers above are simplifying this problem a bit. You are not told if the odd ball is heaver or lighter, which complicates things. The most efficient method is that described by 'questions like this...' as method 2. Split balls into 3 groups and weigh two. The worst outcome is if the groups do not weigh the same, so assume that happens. All you know now is that the odd ball is NOT in the reserved group of 3, so set those aside. You don't know which of the two weighed groups contains the odd ball, so now you have 6. Repeat the first step with groups of 2 balls. Again the worst outcome is that the scales don't balance, so you've eliminated 2 more balls and only know that the odd ball is one of 4. As near as I can tell, you still need 2 more steps now to guarantee finding the odd ball: Choose any two balls from the 4 and compare. If they are the same, the odd ball is in the reserved 2, if they differ the odd ball is one of the two you weighed. Now take one of the two balls that might be odd, and weigh against one of the balls you have been setting aside as 'normal'. By the way, although you now know which ball is odd, you may still not know if it's heavier or lighter. If the last weighing balances, you only know that the other ball is odd, and you would have to weigh it against one of the 'normal' balls to see how it is off. You can do this problem in only 2 weighings if you are told whether the odd ball is heavy or light before you begin.

Maybe I'm slow but....if I put set A and set B on the scale while reserving set C, and if set A is heavier than set B, how do I know if set C is equal to set A or B without weighing it? Notice the question says "more (or less)". In other words, why wouldn't I have to weigh set C? (This is assuming each set is of 3 balls.)

I believe the answer is 2. Step 1: Before weighing anything, you separate the balls into groups of three. Step 2: Put one group of three on one side of the scale, and the other group of three on the other side of the scale, leaving still one other group of three somewhere on the side. ---visualization ooo /\ ooo <--------1st weighing ooo <------side group Step 3: If the scale is balanced that means that the heavier ball is in the side group. At this point, you would weigh any two of the remaining three balls. Again, if the scale is balanced, then you know that the only ball left is the heaviest one. If the scale tips to any particular side, on the other hand, then you know that the heavier ball is on that side. Up to this point the number of weighings is 2. Step 4: if on your first weighing with three balls on each side, the scale tips, then your next weighing will be of any two of the three balls which were on the tipping side of the scale. Again.. if the scale is balanced, then the remaining ball must be the heaviest. And if the scale tips to a side, then you know that side has the heaviest ball. Up to this point the number of weighings is also 2. Therefore the minimum number of weighings is 2. You obviously can get away with 1 weighing, but only if you are lucky; weighing 4 against 4 and hoping that the other ball (not weighed) is the heavier one. Otherwise, starting out weighing 4 against 4 will lead to 3 weighings, therefore that solution is not the optimal one. Even starting out with a 2 against 2 scheme, you can have up to 3 weighings until you are absolutely sure of which ball is the heaviest. So, optimally, you will be weighing 3 balls against 3, and the least amount of times you would have to weigh the balls to know for sure which one is heaviest is 2.

I had this interview question this morning. Those of you who say it has no bearing on determining character are wrong. An arrogant person will present their answer, right or wrong, and say that they are done and it is perfect. It takes humility to consider that your first answer may be wrong, and the interviewer will want to see your process for checking that your answer is correct. Remember, it is the path you take to get to the answer that is more important than getting the answer right.

Given 3 step, divide the balls into 3 groups A, B, C, Not knowing which has the heavier or the lighter ball, #1 Step: scale A vs B, If it balanced then we already know that C has the different weight.(but we still dont know if the ball is heavier or lighter. If it did not balance we will know that the OTHER ball is maybe in group A or B. (Note: e.g. A raises and B dropped) #2 Step: scale A vs C, If it balanced then we will know that the OTHER ball is in group B. If it did not balance e.g A raises and C dropped. we now conclude that C and B has the same weight and the OTHER ball is lighter #3 Step: Using the group A ball. scale the 2 balls, if they balance they we will know that the 3rd ball is the one that is different. if it did not balanced then the side where the ball raises is the OTHER ball because from step 2 we already notice that the ball is Lighter. Problem solved!

Divide the 9 balls into groups of 3 3 - 3 -3 take first 2 groups on the scale. If they balance out: Take the last group of 3 Divide the last group into 1 - 2 Take the 2 (above) one each of the scale. If they balance out, then the '1' is the heavier one else u get the heavier one. Number of scale measurements required = 2

Balance 4 vs 4, - if balance the excess 1 is the lightest or the heaviest. Don't mind which is the heaviest nor the lightest since the question is OR - you can just have one answer.

the minimum would be two. First ball and second ball either one would weight more... since they are asking the "minimum'... if they asked for the maximum then it will take 8 times.

Don't know

Don't know

I don't understand why everyone is confused. The question clearly asks to not only find the odd ball out but to also determine if the odd ball is lighter or heavier. The only assumption is that it is a standard two pan balance. My solution is 4 weighings: 1. Divide 9 balls in three groups of 3. Let's name them A,B,C 2. Weigh any two groups of 3. Let's say A and C. (1st weigh) 3. If A and C are equal then the B group is the culprit. 4. Now lets label the B group as B1, B2, and B3 5. Take either two balls from either A or C and measure against two from B let's say B2 and B3. (2nd weighing). If both are equal then B1 is the odd ball. Now weigh B1+ one good ball against the same two good balls used in the previous weighing and compare to see if the ball is heavier or lighter. (3 weighings) If they are not equal then determine if the B group is currently heavier or lighter. Go to step 6. 6. Switch either B2 or B3 with B1. Let's say we replaced B2 with B1. If the weighing is now equal then B2 is the odd ball out. If the weighing is still unequal then B3 must be the ball. Thus we have used a total of only 3 weighings. Since we made note of the weighing in step 5 we know if the odd ball is heavier or lighter. 7. Now if the 1st weighing (between group A and C) was unequal then we need to determine which is the bad group. Thus we need to weigh one of them against group B (which we know is correct) and then proceed with the steps 2-6. So in this case it is one extra weighing which brings a worst case total of 4 weighings. I hope everything made sense. I don't think its possible to get it in 3 AND also find whether the odd ball is lighter or heavier. One thing is for sure: I would have never solved it during the interview since this took way more than 5 min to figure out.

The comment about the assumptions is absolutely spot on. For example, I like the answer that says ONE step (weighing) but this assumes a balance scale is used not a device that weighs each ball. Based upon a weighing device that weighs each ball and remembering the question is the MINIMUM number of weighings then the answer is THREE - here is the logic. Each weighing weighs one ball. The minimum number of weighings to identify a difference is two, i.e the first two balls are different in weight. The third weighing will confirm which of the previous two is part of the set of eight balls with the other being the odd one out.

I read the question as "determine if the odd ball weighs more or less", not "determine which ball is the odd one out". After re-reading the question, it seems like the word "IF" (i.e. "...to find [IF] the ball weighs more (or less)") or the word "THAT" (i.e. "...to find the ball [THAT] weighs more (or less)") is ommitted (purposefully?). I went about answering the my first interpretation and came up with 2 weighings as the MINIMUM required. I assumed we have a scale that can accurately measure the weight in grams (or whatever unit of measurement needed to accurately measure the ball). Step 1. Weigh 8 balls. Divide the total weight by eight. Step 2. Weigh the remaining ball. If you compare the result from each step you'll know if the ball is heavier or lighter than the others.

I understand the Question to be what the minimum of weightings needed is to find out if the different ball weighs more or less than the other 8. The answer is three. 1. You way 1 ball and get its weight 2. Weigh a second and get its weight 3. If they do not weigh the same way a third to see if the different ball is the heavier or lighter one. Or If they weigh the same weigh all the balls and divide by 9 if it is less than one of the balls you weighed the different ball is lighter. If it is more than one of the balls you weighed the different ball is heavier.

Only 1 step required. Throw all of the balls in a sufficiently deep enough pool of water. The ball that sinks the fastest/slowest is the ball that doesn't weigh the same. If all of the balls float, then it is the ball that is lowest/highest in the water that doesn't weigh the same.

The answer should 1 as it asked "the minimum". When you weight 4 balls on each side of the scale and find it equally weight then the 9th ball is definitely the odd ball. You can always got lucky on the first attempt!

If the question to identify the odd ball (heavy or light) out of 9 balls is read literally, then the answer is 1 weighing (under the most luckiest of circumstances): weigh 2 sets of 4 balls against each other using a double-pan balance and if you're lucky it will weigh evenly, allowing identification of the not-weighed 9th ball as the odd ball. (The question doesn't say you need to identify whether it was heavy or light.) If the question is what is the least number of weighings it takes to identify the odd ball under the least lucky circumstances then the answer is 4, as best I can come up with. 1. Weigh 2 sets of 3 balls against each other, setting aside the 3rd set of 3 balls. The least lucky result ("LLR") is an imbalance. However, this does identify the 3rd unweighed set as all standard balls. 2. Here's where creative problem solving/out-of-box thinking comes into play. Take a red and black marker and mark one of the heavy balls red and one of the light balls black. Switch the marked balls. LLR --> still an imbalance, though imbalance must remain in the same direction since there is only 1 odd ball (yet to be identified). 3. Repeat step 2 (mark one of the unmarked heavy balls red and one of the unmarked light balls black, switch them and reweigh). LLR --> still an imbalance. 4. Take one of the 3 unweighed balls, previously set aside from the 1st weighing, and substitute it for the last remaining unmarked heavy ball. If this last weighing results in an imbalance then the odd ball is the last remaining light ball (and is light, obviously). If the weighing results in a balance, then the removed unmarked heavy ball was the (heavy) odd ball.

I began with the assumption you could do this with a minimum of three, but I now believe it's four. Perhaps I'm over thinking it though, so I'll explain my "solution". Step 1. Start with three balls on either side of the scale, with a third set waiting on the sidelines. If the scale is balanced, you can move onto the three waiting. 2. place one ball on either side, again with the last one waiting. Should the scales be balanced, it's the last one. 3. If they aren't, take the heavier side off, and place the waiting ball on, if they balance. It's the one you just removed. If they're off canter again, it's whichever side was inconsistent. The hitch with the fourth measurement comes due to the little trip up in the question "To find the ball that weighs more (or less)." If you don't know from the start if you're looking for a heavier or lighter ball, should the scales be off on the first measurement, you'll need to replace three of the balls with the reserves to determine which ones are the odd batch out.