Largest Cap Keeping Array Sum Within K

Problem Given an array of positive integers and a target K, reduce the array as little as possible so its total sum is at most K. Every element above a chosen threshold V is capped down to V; elements at or below V are untouched. Find the largest such V — the largest cap is exactly the minimum total reduction that gets the sum under K.

Input / Output

• Input: an integer array arr of positive integers, and an integer target K.
• Output: the largest integer V with sum(min(arr[i], V)) <= K.

Constraints

• 1 <= n <= 10^5; elements can be large, so the running sum may overflow 32-bit — accumulate in 64-bit.
• V is searched over [0, max(arr)]. If sum(arr) <= K already, no capping is needed and the answer is max(arr).
• Confirm with the interviewer whether V must be an integer and how ties are broken — both change the search boundary.

Example

• arr = [10, 20, 30], K = 30 → V = 10: the capped sum is 10+10+10 = 30 <= 30, while V = 11 gives 33 > 30.
• arr = [2, 3, 5], K = 100 → V = 5; the sum is already under K so nothing is capped.