### Leetcode June Challenge - Day 5

**Problem:** LeetCode June Challenge - Day 5

**Ideas:**

- In order to do it randomly, just keep a cumulative array built from w. You want to generate a random number from 0 to the sum of all weights, and then find in which interval [a[i],a[i+1] the random number is contained.
- Note that the sum is less or equal than 1e9, so it fits in an integer.
- Use binary search to find the interval.
- You can use w to store the cumulative array in O(1) space, but I prefer not to modify it.

**Solution**:

```
class Solution {
int a[(int)1e5+1];
int n;
public:
Solution(vector<int>& w) {
a[0] = 0;
n = w.size();
for(int i=0; i<n; ++i) a[i+1] = w[i]+a[i];
}
int pickIndex() {
int r = rand() % a[n];
int lo = 1, hi = n;
while(lo <= hi){
int m = (hi+lo)/2;
if(a[m] <= r) lo = m+1;
else hi = m-1;
}
return hi;
}
};
```