The Old techInterview Forum - Coin weight problem

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 03, 2005

Binary search. O(log N)

zekaric
Monday, January 03, 2005

One, of course.

Keith Neufeld
Monday, January 03, 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 04, 2005

Or something of that nature, 13,7,4,,2,1

6

ehh

Brian Momeyer
Tuesday, January 04, 2005

Or maybe 7, I put 5 twice damnit. It's reaaallly late

Brian Momeyer
Tuesday, January 04, 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 04, 2005