Few companies ask the below brain teaser to the candidates during the interview.
You have 12 bags full of coins. In each bag are infinite coins. But one bag is full of forgeries, and you can’t remember which one. But you do know that genuine coins weigh 1 gram, but forgeries weigh 1.1 grams. You have to identify that bag in minimum readings. You are provided with a digital weighing machine.
But what if it is a coding challenge:
You have N bags full of coins. In each bag are infinite coins. But one bag is full of forgeries, and you can’t remember which one. But you do know that genuine coins weigh 1 gram, but forgeries weigh 1.1 grams. You have to identify that bag in minimum readings. You are provided with a digital weighing machine.
Write a program that can take N as input and the rest solution is generated by it.
The coding solution was originally published in my book “Brain Teasers with Coding For Data Scientist”. Puzzles from that book are published on this link. Also, check my coding puzzle books “Brain Teasers with Coding For Data Scientist 2: 9 New Computational Puzzles” and “Puzzles with Coding: Puzzles for Everyone” and “Computational Puzzles To Flex Your Brain: 50 original puzzles to sharpen computing mind and mathematical skills” at Amazon. For purchasing my books or related queries, feel free to contact me. In these books, you will find interesting brain teasers those are suitable for coders as well as non-coders. Coding solutions are also provided with Python code. So, grab a copy of those books and jump into the world of fascinating and exciting brain teasers.
Solution:
There is only 1 bag with forgeries, so take 1 coin from the first bag, 2 coins from the second bag . . . N coins from the Nth bag and simply weigh the picked coins together.
If there were no forgeries, you know that the total weight should be (1+2+…+n) = n*(n+1)/2 grams.
So, the number difference between them will give the bag number of fake coins.
Coding Solution:
# Finding Bag No filled with fake coins
from random import randint
# N Number of bags
N = int(input("Enter N:(N>0):"))
if N < 1:
print('N should be greater than zero')
exit()
print('Total number of bags:', N)
# r Any random number between 1 & N
r = randint(1, N)
print('random bag number where to put fake coins:', r)
coinArr = []
sumCoin = 0.0
#Putting 1 g coins in each bag except r in which putting 1.1g fake coins
for x in range(1,N+1):
if x == r :
coinArr.append(1.1)
else:
coinArr.append(1)
print('Coin Bags:', coinArr)
#Finding fake coin bags
#Taking k numbers of coin from k bags & weighing them
for k in range(len(coinArr)):
sumCoin += (coinArr[k]) * (k+1)
print('Weight with fake coins:', sumCoin)
#Wanted weight if no coins are fake
actualSumCoin = N * (N+1) / 2;
print('Weight without fake coins:', actualSumCoin)
#Difference between sumCoin and actualSumCoin
diff = sumCoin - actualSumCoin
#round function for correcting floating point difference in Python
fakeBagNo = round(diff,4)*10
print('Bag No. with fake coins:', round(fakeBagNo))
Note : (Keeping non-coder readers in mind, code optimization is not fully utilized.)
Output:
Test Output 1:
Enter N:(N>0):30
Total number of bags: 30
random bag number where to put fake coins: 30
Coin Bags: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1.1]
Weight with fake coins: 468.0
Weight without fake coins: 465.0
Bag No. with fake coins: 30
Test Output 2:
Enter N:(N>0):12
Total number of bags: 12
random bag number where to put fake coins: 4
Coin Bags: [1, 1, 1, 1.1, 1, 1, 1, 1, 1, 1, 1, 1]
Weight with fake coins: 78.4
Weight without fake coins: 78.0
Bag No. with fake coins: 4
