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%).


&nbsp;
Example 1:

Input
["Solution","pickIndex"]
[[[1]],[]]
Output
[null,0]

Explanation
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.


Example 2:

Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.


&nbsp;
Constraints:


	1 &lt;= w.length &lt;= 104
	1 &lt;= w[i] &lt;= 105
	pickIndex will be called at most 104 times.


class Solution(object):
	def __init__(self, w):
		"""
		:type w: List[int]
		"""
		#Cumulative sum
		self.list = [0] * len(w)

		s = 0
		for i, n in enumerate(w):
			s += n
			self.list[i] = s


	def pickIndex(self):
		"""
		:rtype: int
		"""
		return bisect_left(self.list, random.randint(1, self.list[-1]))


# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()
class Solution {

    private int[] prefixSum;
    private Random random;

    public Solution(int[] w) {
        for (int i = 1; i < w.length; i++)
            w[i] += w[i - 1];
        prefixSum = w;
        random = new Random();
    }

    public int pickIndex() {
        int num = 1 + random.nextInt(prefixSum[prefixSum.length - 1]); // Generate random number between 1 and total sum of weights
        int left = 0;
        int right = prefixSum.length - 1;

        while (left < right) {
            int mid = (left + right) / 2;
            if (num == prefixSum[mid])
                return mid;
            else if (num < prefixSum[mid])
                right = mid;
            else
                left = mid + 1;
        }
        return left;
    }
}
class Solution {
public:
    vector<int> cumW;  
    Solution(vector<int>& w) {
        // initialising random seeder
        srand(time(NULL));
        // populating the cumulative weights vector
        cumW.resize(w.size());
        cumW[0] = w[0];
        for (int i = 1; i < w.size(); i++) cumW[i] = cumW[i - 1] + w[i];
    }
    
    int pickIndex() {
        return upper_bound(begin(cumW), end(cumW), rand() % cumW.back()) - begin(cumW);
    }
};
class Solution {
    constructor(nums) {
        this.map = new Map();
        this.sum = 0;
        
        nums.forEach((num, i) => {
            this.sum += num;
            this.map.set(this.sum, i);
        })
    }
    pickIndex = function() {
        const random_sum = Math.floor(Math.random() * this.sum);
        return this.fetchIndexUsingBS(random_sum);
    }
    fetchIndexUsingBS = function(target) {
        const sums = Array.from(this.map.keys());
        let lo = 0,
            hi = sums.length - 1,
            mid;
        
        while(lo <= hi) {
            mid = Math.floor((hi - lo)/2) + lo;
            // if((mid === 0 || sums[mid - 1] < target) && sums[mid] >= target) {
            //     return this.map.get(sums[mid]);
            // }
            if(sums[mid] > target) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}
Random Pick with Weight