Optimise complexity of combinatoric algorithm

Question

I'm struggling to optimise my code on the following problem:

You are given N boxes indexed from 1 to N. Each box contains either no coins or one coin. The number of empty boxes and the number of boxes with one coin are denoted by n0 and n1, respectively. You take a random subset of the boxes where each subset has the same same probability to be selected. The empty set and the set itself are considered a subset.

Given n0 and n1, what is the probability that the total number of coins in the random subset is even?

Constraint: N = n0 + n1 < 100000

EXAMPLES

1

• Input: n0 = 1, n1 = 0
• Output: 1.0
• Explanation: There are two subsets: [] and [0]. Both of them have an even sum.

2

• Input: n0 = 0, n1 = 2
• Output: 0.5
• Explanation: There are four subsets: [], [1], [1], and [1, 1]. The sum of [] and [1,1] is even.

So far I attempted an implementation in Python 3.8, but I think it works ok, but it takes very long to compute for larger numbers.

prob = 0

n0 = 1
n1 = 4

for j in range(0, n1+1):
        if (j % 2 == 0):
            prob += comb(n1, j)

total_prob = (2**n0 * prob) / (2 ** (n0+n1))
total_prob

Answer 1

Assuming your algorithm is correct, total_prob can be determined analytically as follows.

This summation:

prob = 0
for j in range(0, n1+1):
        if (j % 2 == 0):
            prob += comb(n1, j)

Is computing the even terms of binomial coefficients i.e.:

comb(n1, 0) + comb(n1, 2) + ... + comb(n1, J)
    where J is even and J>=n1

It's okay for J > n1, since comb(n1, J) = 0 for J > n1 (definition of nCr)

This sum is simply source:

prob = 2**(n1 - 1)

Substituting for prob in total_prob equation:

total_prob = (2**n0) *(2**(n1-1)) / (2 ** (n0+n1))
total_prob = 2**(n0 + n1 - 1)/(2**(n0+n1))

total_prob = 0.5  (always)