Expected value of balls left, drawing colored balls with 0.5 probability In an urn, there are m red balls and n green balls.
Every minute, you toss a coin and decide which color to draw, then remove one ball of that color from the urn. (e.g. remove one green ball if it is a tail)
What is the expected number of balls left in the jar after you have drawn all red or green balls?
Note that 0 <= m+n <= 10^5
And the solution should be implemented in a way that it return results within 5 second using 1 CPU and 1GB ram.
p.s. this is an interview question I found online (from some interview question banks), tried to attack this problem using binomial / negative-binomial distribution but no luck so far

So you've got $m$ red balls and $n$ green balls. As the coin is fair, $P(Green)=P(Red)=0.5$.
Assume we've had $k$ draws, the probability of drawing $g$ greens and $k-g$ reds is
$P(k,g)={k \choose g}0.5^{k}$, and the number of balls left in the urn is $m+n-k$. The expected value of balls left in the urn (given one color is completely out) is then:
$$\sum_{k=n}^{n+m-1}{(m+n-k){k \choose n}0.5^k}+\sum_{k=m}^{n+m-1}{(m+n-k){k \choose m}0.5^k}$$
So if you're going to solve this numerically, write two loops and you're good.
But wait a second, what if $k$ is too large for a factorial computation? or we fear it might be too slow? This is where the normal approximation becomes handy.
As $p=0.5$ it is proper for any $k \geq 10$, according to the $3\sigma$ rule of thumb. The derivation of the expected number of balls left is very simple.
So, overall, your function should condition of the size of the input: if $m,n<10$ you should sum using the formula above; otherwise, solve using the normal.
