Nudge Values to Agree

Medium

You get an integer array values and two integers, reach and moves. You must make exactly moves moves. In one move you pick an element that has not been touched yet and add to it any integer from -reach to reach inclusive (0 is allowed). Each element changes at most once. Return the largest number of equal elements the array can hold after all the moves.

Example 1

values=[2, 9, 6, 12], reach=3, moves=2 → 3

Move 6 by +3 and 12 by −3: the array becomes [2, 9, 9, 9] with three 9s.

Example 2

values=[5, 5, 20], reach=4, moves=1 → 2

20 is out of reach from the 5s (that takes 15, the limit is 4), so the best is the two 5s already there.

Example 3

values=[1, 3, 5, 7], reach=2, moves=4 → 3

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁵
0 ≤ reach ≤ 10⁵
0 ≤ moves ≤ len(values)

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

Even Out With Increments Medium Rug Over Painted Stretches Medium Richest Row of Houses Medium Most Equal Values on a Budget Hard Nudge Values Into Line Hard

Input

values=[2, 9, 6, 12], reach=3, moves=2

Expected

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