The counterfeit coin problem: A popular MAANG interview question

Analytical part is one important component in the interview or test stage of hiring. All leading companies in software development, data analysis, machine learning, financial engineering, economics, and many other fields require candidates with strong analytical skils.

Employers look for candidates with strong problem-solving and analytical skills. In hiring tests and interviews, they measure the candidate’s ability to identify patterns, rules, and trends from some given information, make connections and find an optimal solution.

We’ll discuss a popular question that often appears in the hiring interviews/tests of companies such as Meta, Apple, Amazon, Netflix, Google (commonly known as the MAANG companies). It’s about finding a counterfeit coin among a number of fair coins. There are many variations of this question. Some are easier and very quick to solve, while others are like pulling teeth.

Let’s start with a simple version and then we’ll increase the complexity of the problem.

The problem: Identifying the counterfeit coin#

We have nine coins that look identical. Out of these nine, there’s one counterfeit coin. We need to identify which coin is counterfeit by comparing the weights of the coins using a weight scale (also commonly referred to as a balance). The goal is to use as few weight comparisons as possible.

We have a balance scale with a left pan and a right pan, and place an equal number of coins in each pan. The scale reveals whether the left or right pan is heavier or whether the two are equal. As mentioned, our goal is to identify the counterfeit coin in as few weight comparisons as possible.

This problem has a number of variations. We’ll discuss some of these below. Let's start with the simplest one.

Three coins problem#

Let’s start with a very simple case with three coins where one coin is counterfeit. Let’s assume we know that the counterfeit coin is heavier than the others. Alternatively, it could be lighter, but the problem and approach to its solution will remain the same.

Let’s number these coins as 1, 2, and 3.

Solution: We can put any two coins on the scale’s left and right pans. Let’s say we place coins 1 and 2 on the scale, and coin 3 is put aside. Here are the possible scenarios:

• Case 1: The scale is balanced. It shows the two coins have the same weight. So both are fair coins. Coin 3 is deemed the counterfeit and is therefore heavier, as mentioned in the problem.

• Case 2: One pan of the scale is heavier. Suppose the pan with coin 1 is lower than the other one. This shows that coin 1 is heavier, and therefore counterfeit.

So with only one weight comparison for each case, we have identified the heavier counterfeit coin.

Three coins problem with one counterfeit coin of unknown weight#

Let’s give it a twist. We have three coins with one counterfeit coin. We need to identify whether the counterfeit coin is heavier or lighter than the others. Again, let's number the coins as 1, 2, and 3.

Solution: We can put any two coins on the scale’s left and right pans. If we place coins 1 and 2 on the scale, and put coin 3 off to the side, here are the possible scenarios:

• Case 1: The scale is balanced. It shows the two coins are fair coins, so coin 3 is deemed counterfeit.

  • We compare coin 3 with either of the fair coins (let’s say with coin 1). If the pan of coin 3 gets lowered, it shows that coin 3 is heavier. On the other hand, if the pan goes up, then the coin 3 is lighter.

• Case 2: One pan of the scale is lower. So coin 3 on the side is a fair coin, and either coin 1 or 2 is the counterfeit. Suppose the pan with coin 1 is lower than the other one. We need to compare coin 1 with the fair coin 3.

  • If the two coins are balanced, that shows coin 1 is fair too. So the counterfeit is coin 2 because it is lighter, (and we saw in the first weighing that coin 2 was lighter than coin 1).

  • On the other hand, if the scale is not balanced, and the pan with coin 1 is still lower than the pan with coin 3, then coin 2 and coin 3 weight the same, and coin 1 is counterfeit and heavier.

So with two weight comparisons, we successfully identified which one is the counterfeit coin and whether it’s heavier or lighter.

Nine coins problem#

Let’s extend the problem to nine coins where one coin is counterfeit. First we solve it assuming that the counterfeit coin is heavier than the other. Alternatively, it could be lighter, but the problem and approach to its solution will remain the same. We need to identify which one is the counterfeit coin with as few weight comparisons as possible.

Let’s number all the coins from 1–9.

Solution: We divide the coins into groups of three coins. Let’s make these groups with the following numbered coins: {1, 2, 3}, {4, 5, 6}, and {7, 8, 9}.

We see that this becomes a similar problem to the three coins problem where individual coins are replaced with a group of coins. It essentially becomes a recursive problem.

We put any two groups of coins on the scale’s left and right pans, and the third set is put aside. Let’s put the coins {1, 2, 3} on the left pan, the coins {4, 5, 6} on the right pan, and keep the coins {7, 8, 9} on the side.

Here are the possible scenarios:

• Case 1: The scale is balanced. It shows the two groups of coins have the same weight. So all six of the coins on the scale are fair. The heavier (counterfeit) coin is among the third group of coins {7, 8, 9} which was kept aside

• To figure out which coin from the three coins {7, 8, 9} is counterfeit, we simply run the three coin problem we’ve already solved in the section above.

• Case 2: One pan of the scale is lower. Suppose the pan with coins {1, 2, 3} is lower than the pan with coins {4, 5, 6}. It shows the heavier (counterfeit) is among the coins {1, 2, 3}, and the rest of the six coins are fair. To find the heavier coin among the three coins, we would run the same problem we did in the original three coins problem. This would require one more weighing.

So with two weight comparisons, we successfully identified the heavier counterfeit coin among the nine coins.

Nine coins problem with one counterfeit coin of unknown weight#

Now let’s look at the nine coins problem with one counterfeit coin. We need to identify which coin is the counterfeit and whether it is heavier or lighter.

We number all the coins from 1–9.

Solution: We again divide the coins into groups of three coins: {1, 2, 3}, {4, 5, 6}, and {7, 8, 9}.

We can put any two sets of coins on the scale’s left and right pans. Let’s say the coins {1, 2, 3} are placed on the left pan, the coins {4, 5, 6} are on the right pan, and the coins {7, 8, 9} are put aside.

Here are the possible scenarios:

• Case 1: The scale is balanced. The two sets of coins on the pans have the same weight, so all six coins on the scale are fair. The heavier (counterfeit) coin is among the third group of coins {7, 8, 9} which was kept aside.

  • To figure out the counterfeit coin from the three coins {7, 8, 9}, it simply becomes the three coins problem with one counterfeit coin. We’ve already solved this problem in the preceding section. It will take two more weight comparisons to identify the counterfeit coin and whether it is heavier or lighter.

• Case 2: One pan of the scale is lower. Suppose the pan with coins {1, 2, 3} is lower than the pan with coins {4, 5, 6}. We know now that the counterfeit coin is one of the six coins on the scale. We know that the coins on the side {7, 8, 9} are fair. We can use these fair coins for comparisons.

• In the second weighing, let’s put the fair coins {7, 8, 9} on the left pan and either set {1, 2, 3} or {4, 5, 6} on the right pan. Let’s suppose we put set {1, 2, 3} on the right pan. It was the heavier one among {1, 2, 3} and {4, 5, 6}. We may have two possibilities.

• The two pans are balanced. This shows the weight of set {1, 2, 3} is the same as that of the fair coins. So all coins from sets {1, 2, 3} and {7, 8, 9} are fair coins. The counterfeit coin is therefore in set {4, 5, 6} and is lighter. The task of identifying the lighter coin among the three coins is the same problem we previously solved. It will take just one more weighing.

• The two pans with coin sets {1, 2, 3} and {7, 8, 9} are not balanced. So the right pan with set {1, 2, 3} will be heavier. It was heavier between {1, 2, 3} and {4, 5, 6} in the previous weighing, so the counterfeit coin, the heavier one, is in set {1, 2, 3}. The task of identifying the heavier coin among the three coins is the same problem we previously solved. It will take just one more weighing.

• So in total we need three weight comparisons to identify the counterfeit coin and to determine whether it’s lighter or heavier than the fair coins.

• Please note, we can switch the cases of heavier or lighter coins, and procedure to identify the coins will remain the same.

So with three weight comparisons, we have successfully identified the counterfeit coin and its type (heavier or lighter) among the nine coins.

A generalized rule#

In the discussion above, we considered the following for the minimum number of weight comparisons for three and nine coins:

• We know the counterfeit coin is heavier or lighter:

  • For three coins, we just need one weighing.

  • For nine coins, we need two weight comparisons.

• We do not know the type (heavier or lighter) of the counterfeit coin:

  • For three coins, we need two weight comparisons.

  • For nine coins, we need three weight comparisons.

Without going into the details of the proof, we have the following generalized rules for the maximum number of coins, if we want to have the minimum possible $n$ weight comparisons:

• We know the counterfeit coin is heavier or lighter: maximum $3^n$coins.

  • For $n=1$ weighing, we can identify the counterfeit coin if we have $3^1 = 3$ coins or less.

  • For $n=2$ weight comparisons, we can identify the counterfeit coin if we have $3^2 = 9$ coins or less.

  • For $n=3$ weight comparisons, we can identify the counterfeit coin if we have $3^3 = 27$ coins or less, and so on.

• We do not know if the counterfeit coin is heavier or lighter: maximum $\frac{3^n - 1}{2}$coins.

  • For $n=1$ weighing, we can identify the counterfeit coin if we have $\frac{3^1 - 1}{2} = 1$ coin.

  • For $n=2$ weight comparisons, we can identify the counterfeit coin if we have$\frac{3^2 - 1}{2} = 4$ coins or less.

  • For $n=3$ weight comparisons, we can identify the counterfeit coin if we have$\frac{3^3 - 1}{2} = 13$ coins or less, and so on.

Conclusion#

Analytical questions are an important part of the hiring interviews of many companies. In software development, analytical skills are vital for problem-solving, algorithm development, optimization, and project planning and execution. Problems like the ones we discussed give us good insight into how to dig deep and come up with solutions using out-of-the-box thinking.

The balanced puzzle or the counterfeit coin problem has a number of variations. We can even extend it to a twelve coins or thirteen coins problem. These are more involved problems and need more careful analysis.

Your next learning steps#

Problem-solving skills are fundamental to computing and algorithms. Educative offers some interesting courses to develop and enhance your problem-solving skills. Please take a look at the following courses offered at Educative: