A handbell choir owns bells whose pitches are the integers in pitches. A tuner can move any bell's pitch up or down by 1 for one unit of work, and has work units in total. She wants as many bells as possible to ring at one common pitch (any integer she likes; bells she does not use keep their pitch and cost nothing).
Return the largest number of bells that can be tuned to a common pitch using at most work units in total.
Examples
Input: pitches = [9, 1, 20, 6, 4], work = 6
Output: 3
Explanation: tune 4, 6 and 9 to pitch 6: 2 + 0 + 3 = 5 units.
Four bells would need at least 10 units.
Input: pitches = [5, 5, 5], work = 0
Output: 3
Input: pitches = [10, 1, 7], work = 3
Output: 2
Constraints
1 <= len(pitches) <= 10**5-10**9 <= pitches[i] <= 10**90 <= work <= 10**15- Target complexity: O(n log n). Trying every group or every target pitch (O(n²) or worse) is too slow for the largest tests.
Goals
- Argue that the best group of values is a contiguous block of the sorted list
- Price a window in O(1) with prefix sums, using its median as the common target