# PROBLEM LINK:

Practice

Contest Link

* Author:* Abhas Jain

*Jatin Yadav*

**Tester:***Abhas Jain*

**Editorialist:**# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

None

# PROBLEM:

Convert an integer array into the zero array by performing some moves. A move consists of choosing k distinct elements and decreasing them by 1 each.

# EXPLANATION:

Decreasing elements of B is the same as increasing A.

The obvious necessary condition is that `sum % k == 0`

and `max[B[i]] <= sum / k`

(Number of moves required).

Let’s prove that it is also sufficient. In every move take the biggest k elements of B and decrease them by 1.

`sum % k == 0`

will hold after each move.

Now, after some move sum will be decreased by k so (sum / k) will decrease by 1. Now `max[B[i]]`

will also decrease by 1. (How?)

**Statement 1** - We know we cannot have more than k elements equal to sum / k. (Otherwise sum \geq (k + 1) * (sum / k) which is not possible.)

Let’s say in the worst case `max[B[i]] == sum / k`

before some move, now we will decrease the first k elements, (k + 1)th element cannot be equal be max[B[i]] in this case (using Statement 1), so max[B[i]] \leq sum / k will also hold after that move.

So the necessary conditions will hold after every move.

Also, to prove that at least k elements will remain non-zero after every move, assume the contradiction that kth element becomes 0 and at least one element remained non-zero during our process. This is also not possible because then at least one element will be greater than sum / k.

This shows that we can perform every move successfully and it completes the proof.