Most Equal Values on a Budget

Hard

You are given an integer array values and an integer budget. In one step you may raise or lower any element by 1, and you may take at most budget steps in total. Return the largest number of equal elements the array can contain once you are done.

Example 1

values=[10, 3, 7, 8], budget=4 → 3

Move 7 and 10 to 8 in 1 + 2 = 3 steps and you get three 8s. Making all four numbers equal takes at least 8 steps.

Example 2

values=[2, 9, 2, 5], budget=0 → 2

No steps are allowed, and 2 already appears twice.

Example 3

values=[1, 100], budget=99 → 2

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁹
0 ≤ budget ≤ 10¹⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Prefix Sum Sorting Sliding Window

Similar problems

Nudge Values Into Line Hard Even Out With Increments Medium Rug Over Painted Stretches Medium Nudge Values to Agree Medium Richest Row of Houses Medium

Input

values=[10, 3, 7, 8], budget=4

Expected

Run checks the first 3 tests in your browser. Submit checks all 99 tests on the server, hidden ones included.