Project Euler/323

https://projecteuler.net/problem=323

Notes

To visualize this problem, think of a coin or stamp collection, where there are slots for coins from each year and you're collecting them as you find them. Except what we're doing here is, starting with a bitvector of 0, called x0, then for multiple rounds, we generate a random number y_i and accumulate any 1s in y_i's bit positions in x_i. The question asks how many rounds it takes, on average, before all the bitvector slots have 1s.

Key insights:

• The probability of a given position k in the final bitvector becoming 1 is identical/independent for all positions, and is 50% (if y is a totally random number, the probability of a given position in its binary representation is 1 is 50%)
• The problem involves independent probabilities of 32 bits, so there will be a 32nd power, somewhere
• The slots all have 50% probability, so there will probably be a (1/2) factor that gets repeated, somewhere

Solution

Link: https://git.charlesreid1.com/cs/euler/src/branch/master/java/Problem323.java