PlayStation

## Interview Question

Programmer Interview

-

# Problem solving: You have 8 identical coins. 1 of which weighs less. You also have a pair of balancing scales. What's the minimum amount of weighs you can have to identify the lighter coin for all possibilities?

Tags:problem solving

3

Minimum is 1 ('the lucky guess method'), but using a specific method the answer is 2. You split the 8 in to 3 groups: Group A: 1,2,3 Group B: 4,5,6 Group C: 7,8 You Weigh Groups: A vs B. If one group is heavier (A or B) then select that group and discard the rest of the coins. e.g. We select A: 1,2,3 Then split the group in to 3 again and weigh 1 vs 2. If either is heavier then that's the heaviest coin. Otherwise if they are equal 3 is the heaviest coin. Likewise if the first weighing is equal, then take group C and weigh that and 1 of those will be the heaviest.

Michael Cox on

1

2 times, 123vs456, if euqal 7v8 123 litter 1vs2 lighter one or 3 on equal situation 456 litter as well

Chitao wang on

2

No. No. No. This is clearly an algorithm related question. You would take 3 tests to achieve the answer. Using binary chop method, you can zero in on the culprit. ie 4/4 - 2/2 - 1/1 Each time one side is lighter, you must assume the lighter coin resides in that collection.

Daniel Grant on