Unknown user: Created page with "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 coll..."

2025-04-21T19:59:13Z

Created page with "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 coll..."

New page

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

==Flags==

{{ProjectEulerFlag}}

Project Euler/323 - Revision history

Unknown user: Created page with "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 coll..."