How many rounds does it take to flip a set of coins such that you only have only one left ? That was the interesting question posed by the following daily coding challenge
You have n fair coins and you flip them all at the same time. Any that come up tails you set aside. The ones that come up heads you flip again. How many rounds do you expect to play before only one coin remains?Write a function that, given n, returns the number of rounds you'd expect to play until one coin remains.
Understanding the problem
A probability of a coin getting heads or tails on a flip is known to be 50/50. We can therefore say if we are given a set of coins and flip them simultaneously, about half of them are 'probably' going to be heads.
Solving it via code
Using the knowledge of probability we can write an algorithm that repeatedly halves the number of coins until we arrive at only 1 coin. We do this whilst keeping track of the number of rounds
Solving it via math
The algorithm that halves the number of coins has similar characteristics to a binary search. A binary search (of a sorted list) involves halving the list until we have found the element we were searching for.
If we had 2 coins, we can reverse our problem and figure out how many rounds it takes to double, triple, quadruple etc. the number of coins. Conversely we can also determine how many rounds it takes to halve the total number of coins until we only have 2 coins left
Finally, we would need to add 1 to our solution to halve 2 coins into 1.
Since we deal with whole coins and odd numbers there could be two different ways to halve a set, and rounding up our solution makes it an approximation.
