Orton K Randy wrote:I was asked the same question in my interview months ago. I am surprised no one in here mentioned the log/exponentiation? After trying out for several no. of balls, you'd have noticed a pattern. Ya don't even think twice. Min no. of weighings(in a physical balance of course) required is
where 'n' is the no. of balls.
log n to the base 2
So if the no. of balls is 4, you need 2 weighings, for 8 you need 3, for 16 you need 4 and so on. Note that for 12 you need 3 and NOT 4. Likewise for 5,6,7 you need only 2 and NOT 3. So in programming terms, it's floor(log n to the base 2).
You might well be aware of this, still this one's for those trying to work out everytime.