Pick a Random Weighted Element

You are given an array of positive integers w where w[i] describes the weight of the ith index.

Implement the function randomPick(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an element is w[i] / sum(w), where i is the index of the element.

The function randomPick() will be called n times (where n is an integer), with all the results stored in an array and then evaluated. This is to ensure that the function works correctly as the output may be different for different runs due to the randomness factor.

For example, if w = [1, 3], then the total weight of the array is 4. The probability of picking index 0 is 1/4 = 0.25 (25%), and the probability of picking index 1 is 3/4 = 0.75 (75%).

Constraints

• 1 <= w.length <= 104
• 1 <= w[i] <= 105
• randomPick() will be called at most 104 times.