Leetcode June Challenge - Day 5

Problem: LeetCode June Challenge - Day 5

Ideas:

  1. 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.
  2. Note that the sum is less or equal than 1e9, so it fits in an integer.
  3. Use binary search to find the interval.
  4. 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;
    }
};