Medium · Hash Maps

Find X to make array sum to K

Given a non-empty array a of positive integers and a target with 1 ≤ target ≤ sum(a), return the smallest integer x with min(a) ≤ x ≤ max(a) such that replacing every element larger than x by x leaves an array sum of at least target.

Examples

Example 1

[1,2,5,8] → 9

Output: x = 3

Example 2

[3,1,4,1,5] → 8

Output: x = 2

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.