179. Top Frequency After Boosts
A game designer tracks the score of each player in the array nums. She has k bonus points to hand out. In one boost she picks any player and raises that player's score by exactly 1; the same player may be boosted many times, and a single boost uses up one bonus point.
After handing out at most k boosts, some score value will be shared by several players. Return the largest possible number of players that can share one common score. Scores only go up, never down, and you do not have to use all the bonus points.
Example 1
- Input:
- nums = [2,5,3,3], k = 4
- Output:
- 3
- Explanation:
Sorted, the scores are 2, 3, 3, 5. Raising both 3s to 5 costs 2 + 2 = 4 boosts, so three players share the score 5. Getting all four to 5 would cost 3 + 2 + 2 = 7, which is more than 4, so the answer is 3.
Example 2
- Input:
- nums = [7,7,7], k = 0
- Output:
- 3
- Explanation:
All three players already share the score 7 and no boost is needed.
Example 3
- Input:
- nums = [1,4,8], k = 5
- Output:
- 2
- Explanation:
Raising 4 to 8 costs 4, giving two players on 8. Including the 1 as well would cost 7 + 4 = 11, which is more than 5, so the answer is 2.
Constraints
1 ≤ nums.length ≤ 105
1 ≤ nums[i] ≤ 105
0 ≤ k ≤ 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 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)