1
class Solution {
2
 public:
3
  vector<int> cumW;
4
  Solution(vector<int> &w) {
5
    // initialising random seeder
6
    srand(time(NULL));
7
    // populating the cumulative weights vector
8
    cumW.resize(w.size());
9
    cumW[0] = w[0];
10
    for (int i = 1; i < w.size(); i++) cumW[i] = cumW[i - 1] + w[i];
11
  }
12

13
  int pickIndex() {
14
    return upper_bound(begin(cumW), end(cumW), rand() % cumW.back()) - begin(cumW);
15
  }
16
};