### PROBLEM LINK:

**Author:** Dmytro Berezin

**Primary Tester:** Prateek Gupta

**Editorialist:** Hussain Kara Fallah

### PROBLEM EXPLANATION

Given an array consisting of **n** integers, Chef wants to make all elements of this array equal. He can apply the following operation:

Pick 2 numbers

**(i,j) :: j = i + D**

Decrementing A_i **OR** A_j by **1** and adding **1** to the other element. Please help chef by telling the minimum number of operations he needs to make all elements equal, or tell that such situation is impossible.

### DIFFICULTY:

### PREREQUISITES:

simple

### EXPLANATION:

Applying our operation any number of times would keep the sum of elements in our array the same. (Since we are subtracting one from an arbitrary number and adding it to another one), so the **sum of our numbers must be divisible by n**

The final value of each element would be equal to \frac{sum}{n}

In any operation chef would choose 2 numbers **(i,j)**:

**(i,j) :: j = i + D**

**j mod D = i mod D**

So you can notice that any pair of elements **A _{i} , A_{j}** such that

**j mod D ≠ i mod D**are independent from each other. (That’s true).

That means that we should group our elements by the remainder of their indexes after dividing by **D**. (And of course) solve each one independently. In fact we will have **D** groups, the **i _{th}** group (0 ≤ i < D) contains all elements

**A**

_{j}(j mod D = i)Let’s tell now about handling each set, applying our operation any number of times would keep the sum of elements in our set the same. So the **sum of elements in each set must be divisible by this set’s size** and of course the result of this division must be equal to \frac{sum}{n} , having one set violating this condition would make Chef’s mission impossible.

Let’s now move to finding the minimum number of operations to fix each set, each set would have 3 kinds of numbers **(numbers > \frac{sum}{n})** and **(numbers < \frac{sum}{n})** and of course **(numbers equal to \frac{sum}{n}) -that we can omit-**.

Let’s process numbers of each set in the same order of the array (from left to right) and separate them into 2 groups as described (first two types since we can omit the third). Maintaining 2 pointers each one iterating on the elements of one group, would just do the job, because if our processed element is less than \frac{sum}{n} then optimal choice would be picking this number along with the closest number bigger than \frac{sum}{n} to the right of it (the same when the opposite happens), and we should add the distance between them for each increment\decrement operation we apply (because we are using elements between them as mediators). After each iteration, one of the numbers referred to by out pointers would reach the desired value, so we move the pointer on. Practically, this part can be done in simpler way (like author’s solution), but this is the detailed explanation. The implementation of this editorial can be found in my code.

### AUTHOR’S AND TESTER’S SOLUTIONS:

**AUTHOR’s solution**: Can be found here

**TESTER’s solution**: Can be found here

**EDITORIALIST’s solution**: Can be found here