510. Sum of Mutated Array Closest to Target

Given an array and a target, choose an integer value v and replace every element greater than v with v (smaller elements are unchanged). Return the value v that makes the resulting array sum as close as possible to the target. If two values are equally close, return the smaller value. Input: '[arr], target'.

Input: '[arr], target'.

Output: Integer — the chosen value v.

Examples

Input: [4,9,3], 10
Output: 3
Explanation: With v=3 sum is 3+3+3=9, closest to 10.

Input: [2,3,5], 10
Output: 5
Explanation: No capping needed.

Input: [60864,25176,27249,21296,20204], 56803
Output: 11361
Explanation: Closest capped sum.

Constraints

• 1<=n<=10^4
• 1<=value,target<=10^5

Asked by