So this is the classic problem of finding a counterfeit coin among a set of coins using only a weighing balance. For completeness, here is one example of such a problem:
A well-known example has nine (or fewer) items, say coins (or balls), that are identical in weight save for one, which in this example is lighter than the others—a counterfeit (an oddball). The difference is only perceptible by weighing them on scale—but only the coins themselves can be weighed. Is it possible to isolate the counterfeit coin with only two weighings?
We are dealing with the case where only one of the coins is counterfeit and we know how it is so (i.e. we know it is heavier/lighter).
My question is, is there a general efficient algorithm to solve the generalized version of this problem for
N coins with one counterfeit. I have been thinking about it and so far I have that if
N is of the form
3^k, then you can find the counterfeit in
⌈log_3_(N)⌉ by splitting them into groups of three recursively. Is this true for all N, not jus those of the from
3^k and if so, can we do better?
I'm voting to close this question as off-topic because belongs to programming.stackexchange.com or maths.stackexchange.com
DhruvPathak Explain. I'm asking about the specific algorithm we could use; how is that not related to stackoverflow. See here and here and here...
Why are you voting this as off-topic? This is about designing an algorithm, which would be equally valid on other sites, and perhaps a better fit on maths, but it's also on topic here.
You say average case. What would be the best and worst cases then?
For random input, ⌈log_3_(N)⌉ is the best, average and worst complexity. In the worst case, we get 2 coins left over, which we cannot check, until we reach the end. This adds at most one extra comparison at the end. The actual worst-case complexity would be ⌈log_3_(N)⌉ * 2 + 1, for keeping the 2 extra coins around.
Why is it off by one?
Not sure. For some randomly generated number of coins it is.