You are the treasurer and you have received information that a counterfeit coin has entered the treasury. All you know is that the counterfeit coin is lighter than the original.
Knowing how many coins you have in total and using only a balance scale, you need to determine the minimum number of weighings to determine which coin is counterfeit before it disappears from the treasury.
Your function must accept only one integer (which will be more than 1) and must output 2 things:
- the minimum number of weighings without lucky chances
- steps on how to find counterfeit coin
Step - a moment when you use balance scale
Without lucky chances means that your number must be the maximum among the minimum steps required. For example let's say that you have 5 coins:
You can split them to 3 groups by 2, 2 and 1 (this isn't a step)
Weighing the groups 2 and 2 (this is a step)
2.1 If they are equal then the remaining coin is counterfeit
2.2. If one of the groups is lighter then the counterfeit coin is in that group
Weigh each remaining coin (this is a step)
3.1 The coin that is lighter is the counterfeit coin
So the minimum number of weighings without lucky chances is 2 but with lucky chances it is 1 because we can find the counterfeit coin at step 2.
The output steps must be easy to understand. Please add a detailed explanation of how to read the output steps. For example the previous example can be represented like this:
[5(2,2) 2(1,1)] - 2
Where the:
[]
- means the possible scenariosx(y,z)
-x
means remaining coins after previous step,(y,z)
means how many coins (fromx
) on each side of balance scale I am weighing'space'
- means the next step/scenario- x
- means the minimum number of weighings without lucky chances
Here is an example with 8
. The output can be shown like this:
[8(3,3) [2(1,1)] [3(1,1)]] - 2
After first step we have two different scenarios because:
- if the 2 groups of 3 are equal then the counterfeit coin is in the group of 2 coins
- if the 2 groups of 3 aren't equal then the counterfeit coin is on one of the groups of 3
It is enough to to weigh only 2 different coins in each scenario to find the counterfeit coin. Regardless of the scenario, the minimum number of weighings without lucky chances is 2
Here are the possible outputs for 2 to 9 coins:
2 --> [2(1,1)] - 1
3 --> [3(1,1)] - 1
4 --> [4(2,2) 2(1,1)] - 2
5 --> [5(2,2) 2(1,1)] - 2
6 --> [6(2,2) 2(1,1)] - 2
7 --> [7(3,3) 3(1,1)] - 2
8 --> [8(3,3) [2(1,1)] [3(1,1)]] - 2
9 --> [9(3,3) 3(1,1)] - 2
You can output any of the possible steps of how to find the counterfeit coin. For example for 10
we have 5 different scenarios. You can output any of them:
10 --> [10(5,5) 5(2,2) 2(1,1)] - 3
10 --> [10(4,4) [2(1,1)] [4(2,2) 2(1,1)]] - 3
10 --> [10(3,3) [3(1,1)] [4(2,2) 2(1,1)]] - 3
10 --> [10(2,2) [2(1,1)] [6(3,3) 3(1,1)]] - 3
10 --> [10(1,1) 8(3,3) [2(1,1)] [3(1,1)]] - 3
The shortest code in each programming language wins!