363. Spending Ceiling
A city office receives spending requests, where nums[i] is the amount asked for by the i-th department. The office wants to choose one ceiling value c (a whole number, 0 or more) and cut every request that is larger than c down to c, while smaller requests stay as they are.
The total after the cuts should be as close as possible to the available budget target. Return the ceiling c for which the absolute difference between the new total and target is smallest. If two ceilings give the same difference, return the smaller one. The ceiling may be larger than every request.
Example 1
- Input:
- nums = [5,2,8], target = 12
- Output:
- 5
- Explanation:
With c = 5 the capped requests are 5, 2 and 5, which add up to exactly 12, so the answer is 5.
Example 2
- Input:
- nums = [10,10], target = 9
- Output:
- 4
- Explanation:
With c = 4 the total is 8 and with c = 5 the total is 10; both are 1 away from 9. The tie goes to the smaller ceiling, so the answer is 4.
Constraints
1 ≤ nums.length ≤ 105
1 ≤ nums[i] ≤ 108
1 ≤ target ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log M), where M is the largest request
- Space
- O(1)