Increase Values to Maximize One Frequency
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
In one operation, increment an entry of `nums` by one. Use at most `k` operations and return the greatest achievable frequency of any value.
```cpp
class Solution {
public:
int maxFrequency(vector<int>& nums, int k);
};
```
### Examples
**Example 1:**
```text
nums = [2,3,6], k = 7
Output: 3
Explanation: Raising 2 and 3 to 6 costs 4+3=7.
```
**Example 2:**
```text
nums = [2,5,9], k = 2
Output: 1
Explanation: Every pair needs at least 3 increments to become equal.
```
### Constraints
- `1 <= nums.length <= 10^5`.
- `1 <= nums[i] <= 10^5`.
- `1 <= k <= 10^5`.
### Clarifying Questions
Only increments are allowed. The result is a frequency count, not a chosen value or the altered array.
```hint Inspect the structure
Which changes are legal, and is the requested output a value, an arrangement, or a frequency?
```
### Reasoning checkpoints
- Use only increments and stay within the shared operation budget.
- Prove the maximum attainable frequency without prescribing a target value.
### Optional extensions
How could binary search on the desired frequency use prefix sums instead?
Overview: Increase Values to Maximize One Frequency. In one operation, increment an entry of nums by one. Use at most k operations and return the greatest achievable frequency of any value.
