I was practicing for an upcoming interview on HackerRank yesterday night. One of these problems was difficult for me to solve and was phrased something like this:

You have an m by n grid of bubble wrap. At random, you try to pop one of the bubbles, which takes one second regardless of if there is a bubble there. How long will would you expect to take in order to pop all of the bubbles?

For example:

• A 1 by 1 grid will take 1 second
• A 1 by 2 grid will take 3 seconds
• A 2 by 2 grid will take 8.3 seconds

The problem then linked to the Wikipedia page for expected value, suggesting the use of a formula from that page in order to implement a solution. However, I'm not sure how to apply the information on the page in order to create a solution.

I tried searching for a more concise solution, but I couldn't find anything. However, I checked the discussions for the problem on HackerRank and I some people saying that the problem is also known as the coupon collector's problem.

After reading the Wikipedia page, I found that the formula for the expected number of draws is n * H_n, where n is the number of coupons to collect and H_n is the n-th harmonic number.

I'm not sure what a harmonic number is either, but Wikipedia explains:

In mathematics, the n-th harmonic number is the sum of the reciprocals of the first n natural numbers:
$$ H_n = 1 + \frac 1 2 + \frac 1 3 + ... + \frac 1 n = \sum_{k=1}^n \frac 1 k $$

So, the solution is:

main :: IO ()
main = do
  m <- read <$> getLine
  n <- read <$> getLine
  print (expected (m * n))

expected :: Int -> Float
expected n =
  fromIntegral n * sum [ 1.0 / (fromIntegral k) | k <- [1..n] ]