We will see what fake coin problem is and will also see an efficient method to solve the problem.

Table of contents:

1. What is Fake Coin Problem?
2. Brute force method
3. Decrease and Conquer Technique
4. Time and Space Complexity

What is Fake Coin Problem?

Fake coin problem is an interesting problem in which we have to find a fake coin out of a number of coins, which is assumed to be lighter than the real coins using just a balance scale, which can be used to compare the weights of two piles of coins.

There can be two ways of solving this problem , one can be the brute force one and the other one will be the more efficient one.
We will analyse both one by one.

Brute force method

In this method, we will pick up a coin at random and use it as a test coin for other remaining coins.
We will test it with other coins one by one and if in any case the balance is seen to be tilting on one side then, the fake coin will be present in that case and the one which is lighter will be the fake coin as per our rule.
If the test coin itself is lighter then, we will be able to identify on the first go, as the balance scale will get tilted towards the heavier coin.

Algorithm:-

1.First coin from the top(any coin can be test coin here we are taking the first coin) will be chosen as the test coin against which every other coin will be tested.
2.Firstly, we will compare first and second coin, if they will be balanced, then we will proceed to compare first and third coin, and then first and fourth coin and then we carry on subsequently until we get an unbalance in the balance scale.
3.Then the coin with which we have compared the first coin will be our fake coin.

Example:-

Suppose the weights of the coin are 2 units for the real one and 1 units for the fake one and there are 10 coins stored in form of a pile, of which 6th coin is the fake one(which we don't know beforehand, this information is given here just for the sake of understanding what is happening).
According to the above algorithm, we will first compare the first coin with second coin in the pile, and then carry on subsequently until we get any unbalance and in this case that will be the 6th coin, thus, 6th coin will be the fake one.

Implementation:-

import random
real_coin = 1
fake_coin = 0

#Shuffles the coin so that we stimulate the environment that we don't know #the fake coin
def randomize_coins(n):  
    """A shuffled list of (n-1) real coins and 1 fake coin."""
    global coins 
    coins= [real_coin] * (n - 1) + [fake_coin] * (1)# Generate an array of coins
    random.shuffle(coins)
    print(coins)
    return coins
def testing_fake_one(n):
    for i in range(1,n):
        if coins[0]==coins[i]:
            pass
        elif coins[0]<coins[i]:
            return print(1,"th coin is the fake one")
        else:
            return print(i+1,"th coin is the fake one")
n=int(input("Enter the number of coins:"))
randomize_coins(n)
testing_fake_one(n)

Complexity:-

Time complexity for the implementation of the above algorithm is O(n), where n is the number of coins, out of which fake coin is to be determined.
Space complexity is also O(n).

Decrease and Conquer Technique

The type of Decrease and Conquer technique we are going to use is the one in which we divide the problem size by a constant factor to get certain subdivisions and ignore the rest while solving for the one subdivision which is suitable for our algorithm like binary search, while in the case of divide and conquer we try to solve for all the subdivisions of the problem like in Merge Sort.

Here is an algorithm:

1. Take number of coins, n, as an input, along with their weight with fake one having different weight than the real ones.
2. If only one coin is there then that will be the fake coin.
3. If more than one coins are there then divide the coins into piles of A = ceiling(n/3), B=ceiling(n/3), and C= n-2* ceiling(n/3).
4. Weigh A and B, if scale balances then repeat from the first step with total number of coins equalling number of coins in C.
5. If the scale unbalances then repeat from the step 1, with the lighter of A and B.

If n mod 3=0, then three piles will be of size k,k,k.
If n mod 3=1, then three piles will be of size k,k,k+1.
If n mod 3=2, then three piles will be of size k+1,k+1,k.

E.g.:- Suppose there are 12 coins of which 11 are real and one of them is lighter, then, find out the fake one in least weighings possible.
Since, there are 12 coins which is divisible by 3, therefore, we divide by 3, and make piles of size 4, namely A,B and C.
Now, only 3 situations are possibl

1. Compare A and B, weight of A>B.
2. Weight of A<B.
3. Weight of A=B.
   If A>B, then, clearly the counterfeit coin is in pile B, again, since pile B has 4 coins and we know that 4 mod 3=1, thus, we create piles of size 1,1, and 2.
   Similarly, if A<B, then, clearly the counterfeit coin is in pile A and we will do the same step as mentioned in A>B.
   And, if A=B, then, clearly the counterfeit coin is in pile C and again we will again divide the pile C in groups as mentioned in the case where A>B.
   We compare piles of size 1 and 1. Again, only 3 situations are possible, i.e. if one of them is lighter then that one is the fake coin or if both are equal in weight then, fake coin must be in the pile having size 2 and, thus, we again, divide 2 coins into 3 groups namely of size 1,1 and 0, and we compare the piles of size 1, the one which is lighter is the fake one.

Implementation:-

import random
real_coin = 1
fake_coin = 0

def randomize_coins(n):  
    global coins 
    coins= [real_coin] * (n - 1) + [fake_coin] * (1)
    random.shuffle(coins)
    print(coins)
    return coins
def testing_fake_one(x,y,n):
    if n==1:
        print(1,"st coin is the fake one")
    else:
            if n % 3==0 or n%3==1:
                A=[coins[i] for i in range(x,x+(y-x)//3 )]
                B=[coins[i] for i in range(x+(y-x)//3,x+2*(y-x)//3)]
                C=[coins[i] for i in range(x+2*(y-x)//3,y)]
                coins_index_A=[i+1 for i in range(x,x+(y-x)//3)]
                coins_index_B=[i+1 for i in range(x+(y-x)//3,x+2*(y-x)//3)]
                coins_index_C=[i+1 for i in range(x+2*(y-x)//3,y)]
                if sum(A)<sum(B):
                    if len(A)>1:
                        testing_fake_one(x,x+(y-x)//3,(y-x)//3)
                    if len(A)==1:
                        return print(coins_index_A[0],"th coin is the fake coin")
                elif sum(A)>sum(B):
                    if len(B)>1:
                        testing_fake_one(x+(y-x)//3,x+2*(y-x)//3,(y-x)//3)
                    if len(B)==1:
                        return print(coins_index_B[0],"th coin is the fake coin")
                else:
                    if len(C)>1:
                        testing_fake_one(x+2*(y-x)//3,y,y-2*(y-x)//3-x)
                    if len(C)==1:
                        return print(coins_index_C[0],"th coin is the fake coin")
            else:
                A=[coins[i] for i in range(x,x+(y-x)//3+1)]
                B=[coins[i] for i in range(x+(y-x)//3+1,x+2*(y-x)//3+1)]
                C=[coins[i] for i in range(x+2*(y-x)//3+1,y)]
                coins_index_A=[i+1 for i in range(x,x+(y-x)//3+1)]
                coins_index_B=[i+1 for i in range(x+(y-x)//3+1,x+2*(y-x)//3+1)]
                coins_index_C=[i+1 for i in range(x+2*(y-x)//3+1,y)]
                if sum(A)<sum(B):
                    if len(A)>1:
                        testing_fake_one(x,x+(y-x)//3+1,(y-x)//3+1)
                    if len(A)==1:
                        return print(coins_index_A[0],"th coin is the fake coin")
                elif sum(A)>sum(B):
                    if len(A)>1:
                        testing_fake_one(x+(y-x)//3+1,x+2*(y-x)//3+1,(y-x)//3)
                    if len(A)==1:
                        return print(coins_index_B[0],"th coin is the fake coin")
                else:
                    if len(A)>1:
                        testing_fake_one(x+2*(y-x)//3+1,y,y-2*(y-x)//3-1-x)
                    if len(A)==1:
                        return print(coins_index_C[0],"th coin is the fake coin")
            
n=int(input("Enter the number of coins:"))
randomize_coins(n)
testing_fake_one(0,n,n)

Time and Space Complexity

Time complexity for running this algorithm is O(log n), given, we assume that we can somehow find weight or sum in constant time.
Space complexity is O(log n), depending upon the number of coins.

With this article at OpenGenus, you must have the complete idea of Fake Coin Problem.