Avoid Minimums

The clean way to solve this is to stop thinking about individual operations first. Pick the final value, then the scheduling problem becomes much smaller.

Suppose the final equal value is $x$. Since we can only increase values, we need $x >= max(a)$. The number of operations is forced:

$ops = n*x - S$

where $S$ is the sum of the array. So feasibility for this $x$ just means $ops <= k$.

Now the real question is: among those forced operations, how many can earn coins?

Coin operations vs coinless operations

An operation earns a coin exactly when the chosen element is strictly greater than the current minimum before the increment.

So the only bad operations are the ones where we increment an element currently equal to the minimum. Call those coinless operations.

Then:

$coins = ops - coinless$

So we want to minimize the number of coinless operations.

Let:

• $m$ = initial minimum value
• $c$ = number of elements initially equal to $m$

Assume first that $x > m$. If $x = m$, the array is already equal and the answer is just $0$.

The unavoidable coinless operations

The array minimum starts at $m$ and must end at $x$. Since each operation increases one element by exactly $1$, the global minimum must move from:

$m -> m+1 -> m+2 -> ... -> x$

For each of these $x-m$ level increases, some element that is currently minimum must be incremented. That operation gives no coin. So we already need at least:

$x-m$

coinless operations.

But there is one more annoying detail. If $c$ elements start at the minimum $m$, then all $c$ of them must eventually leave value $m$. The operation that makes the minimum finally rise from $m$ to $m+1$ accounts for one of them. The other $c-1$ minimum elements also need their first increment from $m$ to $m+1$, and those increments are also coinless.

So any strategy needs at least:

$coinless >= (x-m) + (c-1)$

That is the tax. No clever scheduling dodges it.

Why this lower bound is tight

Now for the fun part: we can actually hit that bound exactly.

Pick one element that initially equals $m$ and keep it untouched as an anchor. While this anchor stays at $m$, every element above $m$ can be increased all the way to $x$, and every one of those operations earns a coin.

For the other elements that also started at $m$:

• their first increment from $m$ to $m+1$ gives no coin
• after that, they are greater than the anchor, so all remaining increments to $x$ give coins

After everyone else reaches $x$, raise the anchor from $m$ to $x$. It is the minimum the whole time, so those $x-m$ operations give no coins.

Total coinless operations:

$c-1 + x-m$

Exactly the lower bound. So this is optimal.

Therefore, for a fixed final value $x > m$:

$coins = (n*x - S) - ((x-m) + (c-1))$

Choosing the best final value

First, we must be able to make the array equal at all. The smallest possible final value is the current maximum $M = max(a)$. The required operations are:

$need = n*M - S$

If $need > k$, print $-1$.

Otherwise, which final value should we choose?

For $x > m$, increasing $x$ by $1$ adds $n$ total operations. But it adds only $1$ extra unavoidable coinless operation, because the anchor must climb one more step. So coins increase by $n-1$.

Since $n >= 2$, larger feasible $x$ is always at least as good, and usually strictly better. So we take the largest equal value reachable with at most $k$ operations:

$x = floor((S+k)/n)$

If $x = m$, no full useful layer can be completed, so the answer is $0$. Otherwise use the formula above.

Algorithm

For each test case:

1. Read the array.
2. Compute $S$, $m$, $M$, and $c$.
3. If $n*M - S > k$, output $-1$.
4. Set $x = floor((S+k)/n)$.
5. If $x = m$, output $0$.
6. Otherwise output:

$n*x - S - ((x-m) + (c-1))$

Complexity

Sorting is not needed. We only scan the array once.

Time: $O(n)$ per test case.

Memory: $O(1)$ besides the input array, and you can even avoid storing it.