type Solution struct {
prefixSum []int
}
func Constructor(w []int) Solution {
prefixSum := make([]int, len(w))
for i, e := range w {
if i == 0 {
prefixSum[i] = e
continue
}
prefixSum[i] = prefixSum[i-1] + e
}
return Solution{prefixSum: prefixSum}
}
func (t *Solution) PickIndex() int {
rand.Seed(time.Now().UnixNano())
n := rand.Intn(t.prefixSum[len(t.prefixSum)-1]) + 1
lo, hi := 0, len(t.prefixSum)-1
for lo < hi {
mid := lo + (hi-lo)>>1
if t.prefixSum[mid] == n {
return mid
} else if t.prefixSum[mid] < n {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}