33/

Use binary search on a transformed array, where numbers represent cumulative distribution function, i.e., a value at index k is the sum of weights for indices 0 to k:

weights = [1, 2, 3, 4, ...]
cdf = [1, 3, 6, 10, ...]

Use a random number generator to get a random integer between 0 and the sum of all weights (excluded).

Complexity:

• time: O(n + log(n)) ~ O(n) to build CDF and run binary search
• space: O(n) to store CDF

Optimizations:

• If the code re-uses the same weights to generate a large number of random numbers M, i.e., M >> N, then one can build the CDF once and reuse it M times to drive the time complexity to O(log(N)) and get rid of O(M) factor.