Few companies ask the below brain teaser to the candidates during the interview.
You have 100 coins laying flat on a table, each with a head side and a tail side. 10 of them are heads up, rest are tails up. You can’t feel, see or in any other way find out which 10 are heads up.
Your goal: split the coins into two piles in such a way that there are the same numbers of heads-up coins in each pile.
But what if it is a coding challenge:
You have an N coins laying flat on a table, each with a head side and a tail side. M of them are heads up, rest are tails up. You can’t feel, see or in any other way find out which M are heads up.
Your goal: split the coins into two piles in such a way that there are the same numbers of heads-up coins in each pile.
Write a program that can take N as an input and the rest solution can be generated by a program.
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:
1.) If there are M heads-up coins in N coins then pick randomly M coins from the given N coins and create two piles. (M coins, (N-M) coins)
2.) Flip all coins from a pile of M coins. You’re done. You have successfully created two piles so that there are the same numbers of heads-up coins in each pile.
Coding Solution:
from random import randint
import array as arr
# Random function that returns N Coins with M Heads
def random_coins():
# generate random number either 1 or 0
r = randint(0, 1)
# return Head if we got number 1, else return T
return H if (r == 1) else T
# Generate Two Piles with Same Number of Heads-up Coins
if __name__ == '__main__':
# Head
H = 1
# Tail
T = 0
head_count = tail_count = 0
#Number of coins, let's take 100
N = int(input("Enter Number(N):"))
coins = []
for i in range(N):
val = random_coins()
if val == 1:
head_count += 1
coins.append(1)
else:
tail_count += 1
coins.append(0)
print('Randomly Generated Coins')
print(coins)
print('In single pile of', N, 'coins:', head_count, 'are Heads and ', tail_count, ' are Tails')
print('***Solution for splitting the coins into two piles***')
pile1_coins = coins[0:head_count]
print('Size of 1st piles coins:',len(pile1_coins))
print('1st piles coins:', pile1_coins)
pile2_coins = coins[len(pile1_coins):N]
print('Size of 2nd piles coins:', len(pile2_coins))
print('2nd piles coins:', pile2_coins)
pile1_coins_head = pile2_coins_head = 0
print('flip all coins of 1st pile')
for g in range(len(pile1_coins)):
if pile1_coins[g] == 1:
pile1_coins[g] = 0
else:
pile1_coins[g] = 1
print('1st piles coins after a flip:', pile1_coins)
for j in range(len(pile1_coins)):
if pile1_coins[j] == 1:
pile1_coins_head += 1
for k in range(len(pile2_coins)):
if pile2_coins[k] == 1:
pile2_coins_head += 1
print('Number of coins with head in 1st pile:',pile1_coins_head)
print('Number of coins with head in 2nd pile:',pile2_coins_head)
Note : (Keeping non-coder readers in mind, code optimization is not fully utilized.)
Test output : 1
Enter Number(N):100
Randomly Generated Coins
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0]
In single pile of 100 coins: 43 are Heads and 57 are Tails
***Solution for splitting the coins into two piles***
Size of 1st piles coins: 43
1st piles coins: [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0]
Size of 2nd piles coins: 57
2nd piles coins: [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0]
flip all coins of 1st pile
1st piles coins after a flip: [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1]
Number of coins with head in 1st pile: 26
Number of coins with head in 2nd pile: 26
Test output : 2
Enter Number(N):50
Randomly Generated Coins
[0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1]
In single pile of 50 coins: 26 are Heads and 24 are Tails
***Solution for splitting the coins into two piles***
Size of 1st piles coins: 26
1st piles coins: [0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1]
Size of 2nd piles coins: 24
2nd piles coins: [1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1]
flip all coins of 1st pile
1st piles coins after a flip: [1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0]
Number of coins with head in 1st pile: 14
Number of coins with head in 2nd pile: 14
