## Algorithm

Problem Name: 528. Random Pick with Weight

You are given a 0-indexed array of positive integers `w` where `w[i]` describes the weight of the `ith` index.

You need to implement the function `pickIndex()`, which randomly picks an index in the range `[0, w.length - 1]` (inclusive) and returns it. The probability of picking an index `i` is `w[i] / sum(w)`.

• For example, if `w = [1, 3]`, the probability of picking index `0` is `1 / (1 + 3) = 0.25` (i.e., `25%`), and the probability of picking index `1` is `3 / (1 + 3) = 0.75` (i.e., `75%`).

Example 1:

```Input
["Solution","pickIndex"]
[[[1]],[]]
Output
[null,0]

Explanation
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.
```

Example 2:

```Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.
```

Constraints:

• `1 <= w.length <= 104`
• `1 <= w[i] <= 105`
• `pickIndex` will be called at most `104` times.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
private int[] prefixSum;
private int totalPrefixSum;

public Solution(int[] w) {
this.prefixSum = new int[w.length];
int currPrefixSum = 0;
for (int i = 0; i < w.length; i++) {
currPrefixSum += w[i];
this.prefixSum[i] = currPrefixSum;
}
this.totalPrefixSum = currPrefixSum;
}

public int pickIndex() {
double randomTarget = this.totalPrefixSum * Math.random();
int left = 0;
int right = this.prefixSum.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (randomTarget > this.prefixSum[mid]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
``````
Copy The Code &

Input

cmd
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[1,3]],[],[],[],[],[]]

Output

cmd
[null,1,1,1,1,0]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const Solution = function(w) {
this.a = []
let sum = 0
for (let i = 0, len = w.length; i < len; i++) {
sum += w[i]
this.a[i] = sum
}
}

Solution.prototype.pickIndex = function() {
const len = this.a.length
const sum = this.a[len - 1]
const rand = ((Math.random() * sum) >> 0) + 1
let l = 0,
h = len - 1
while (l < h) {
const mid = (l + h) >> 1
if (this.a[mid] === rand) return mid
else if (this.a[mid] < rand) l = mid + 1
else h = mid
}
return l
}
``````
Copy The Code &

Input

cmd
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[1,3]],[],[],[],[],[]]

Output

cmd
[null,1,1,1,1,0]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:

def __init__(self, w):
self.ranges, sm = [], 0
for weight in w:
self.ranges.append([sm, sm + weight])
sm += weight
self.mn, self.mx = 1, sm
def pickIndex(self):
num, l, r = random.randint(self.mn, self.mx), 0, len(self.ranges) - 1
while l <= r:
mid = (l + r) // 2
if self.ranges[mid][1] < num:
l = mid + 1
elif num <= self.ranges[mid][0]:
r = mid - 1
else:
return mid
``````
Copy The Code &

Input

cmd
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[1,3]],[],[],[],[],[]]

Output

cmd
[null,1,1,1,1,0]

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0528_RandomPickWithWeight
{

public _0528_RandomPickWithWeight(int[] w)
{
prefixSums = new int[w.Length];
for (int i = 0; i < w.Length; i++)
{
totalSum += w[i];
prefixSums[i] = totalSum;
}
random = new Random();
}

public int PickIndex()
{
var target = random.Next(totalSum) + 1;

int lo = 0, hi = prefixSums.Length - 1;
while (lo <= hi)
{
int mid = lo + (hi - lo) / 2;
if (target == prefixSums[mid]) return mid;
if (target > prefixSums[mid])
lo = mid + 1;
else
hi = mid - 1;
}

return lo;
}
}

}
``````
Copy The Code &

Input

cmd
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[1,3]],[],[],[],[],[]]

Output

cmd
[null,1,1,1,1,0]