504. Random Pick with Weight (Deterministic Queries)

Given an array of positive weights, the probability of picking index i is proportional to its weight. The standard implementation builds prefix sums and, for a target in [1, total], returns the smallest index whose prefix sum is >= target. To make this deterministic, you are given a list of integer query targets; for each target return the index that would be picked. The input is JSON {w, queries}. Return the picked indices as an array.

Input: JSON {w, queries}.

Output: Array — the picked index per query.

Examples

Input: {"w":[1,3,2],"queries":[1,2,4,6]}
Output: [0,1,1,2]
Explanation: Prefix sums [1,4,6]; targets map to those indices.

Input: {"w":[1],"queries":[1]}
Output: [0]
Explanation: Single weight.

Constraints

• 1<=n<=10^4
• 1<=weight<=10^5
• 1<=target<=total

Asked by