# Leetcode 528 - Random Pick with Weight

Note:

• By the description, $P_{w[i]} = \frac{w[i]}{sum(w)}$.
• In order for this to work, we have to make a presum[].
• Imagine each w[i] occupy an interval on x-axios, then if we generate a random, the first element in presum[] that is bigger than random is our ans.

Question:

You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.

You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).

For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).

Example:

Code: