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\ast 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] ]