Coin weight problem I've scanned through the articles, and I don't see this one, so here goes. You have 100 machines that produce an identical coin.  Each coin is supposed to weigh 1 ounce exactly.  During quality control on a batch of coins, it is determined that one machine is producing a coin that weighs 1.01 ounces. Using a bathroom-type scale (sensitive enough to accurately measure a 1.01 ounce coin) how many weighings do you have to make taking coins from the machines to find the machine producing the heavy coin? ICSH Monday, January 3, 2005 Binary search.  O(log N) zekaric Monday, January 3, 2005 One, of course. Keith Neufeld Monday, January 3, 2005 1) Weigh 50- eliminate half 2) Weight 25 3) Weigh 13 4) Weigh 7 5) Weigh 3 5) Weigh 2 Pick One 5 Brian Momeyer Tuesday, January 4, 2005 Or something of that nature, 13,7,4,,2,1 6 ehh Brian Momeyer Tuesday, January 4, 2005 Or maybe 7, I put 5 twice damnit.  It's reaaallly late Brian Momeyer Tuesday, January 4, 2005 One: 1 coin from the first, 2 from the second, ... 100 from the 100th, put all on the scale, see how much it exceeds 5050 ounces (the sum of 1 to 100), divide the result by 0.01 to get which machine is faulty. Tamas Hauer Tuesday, January 4, 2005   Fog Creek Home