# Given a list of ints, write "getRandom" function

• given a list of integers as such: [5,2,3,1] write getRandom() function where:
total = 1+2+3+5 = 11
1 is given with 1 / 11 chance
2 is given with 2 / 11 chance
3 is given with 3 / 11 chance
5 is given with 5 / 11 chance

Can you do this in constant space?

``````    public class RandomeClass {
private int[] dp;
private int sum;
private Random random = new Random();
private int[] nums;
public RandomeClass(int[] nums) {
this.nums = nums;
int len = nums.Length;
dp = new int[len];
for (int i = 0; i < len; i++) {
sum += nums[i];
dp[i] = sum;
}
}

public int GetRandom() {
int low = 0;
int high = dp.Length;
int val = random.Next(sum);

while (low < high-1)
{
int mid = low + (high - low) / 2;
if (dp[mid] <= val)
{
low = mid;
}
else
{
high = mid;
}
}

if (dp[low] > val)
{
return nums[low];
}
else if (dp[high] > val) {
return nums[high];
}
else
{
return nums[high+1];
}
}
}
``````

• That's also the best solution I could come up with (O(n) for initialization and O(log n) for picking a number).

Note that you are not using constant space here, but you could just reuse the nums array instead of creating a new one to get there.

@bsm can there be duplicates in the list ?

``````int GetRandom(int[] arr){
int sum = arr[0];
int len = arr.Length;
var rand = new Random();
int result = arr[0];
for(int i = 1;i<len;i++){
sum+=arr[i];
if(rand.NextInt(sum) < arr[i]){
result = arr[i];
}
}
return result;
}
``````

• Constant space

``````def getRandom(a):
s = sum(a)
i = 0
r = random.random() * s
while r >= 0:
if r - a[i] <= 0:
return a[i]
else:
r -= a[i]
i += 1
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.