1
class Solution {
2

3
  private int[] prefixSum;
4
  private Random random;
5

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

12
  public int pickIndex() {
13
    int num =
14
        1
15
            + random.nextInt(
16
                prefixSum[
17
                    prefixSum.length
18
                        - 1]); // Generate random number between 1 and total sum of weights
19
    int left = 0;
20
    int right = prefixSum.length - 1;
21

22
    while (left < right) {
23
      int mid = (left + right) / 2;
24
      if (num == prefixSum[mid]) return mid;
25
      else if (num < prefixSum[mid]) right = mid;
26
      else left = mid + 1;
27
    }
28
    return left;
29
  }
30
}