I gave this contest today, so thought to share this editorial.
Here we go,
So let me first give a brief intro about the problem statement, so we are given an array of size n. We have to print minimum operations with which we can make all the elements of the array equal.
Operation allowed:
Select I ( 0≤i<N) and add it to either i+1 or i-1 i.e., to its neighbor.
APPROACH:
- Firstly we will calculate the sum of the array.
- Now, try to find that into how many parts this sum can equally be divided. For example: 4,2,1,3,2 . sum = 12. so, it can be divided into {4,2} and {1,3,2}. hence we will dissolve these subarrays only to make each element perfectly equal.
CODE:
Iterate from N till 0, we are trying to find, into how many elements, the sum can be divided, so in the above example, 12 can be divided perfectly by 4,3,2,1. So, we will check all the subarray of these sizes and check whether it is possible to make them equal or not.
As soon as we find sum%N==0, do this operation, i.e., divide this subarray into elements having sum = goal (goal = sum/N)
If it is not possible, move on to the next value of the goal.
DRY RUN:
Input :
N = 5
int arr[] = {4,2,1,3,2}
sum = 12
- N == 5 (12%5!=0) therefore continue
- N==4 (12%4==0) so we will move further
current = 0, current+4 >goal(12/4 = 3) , therefore not okay, we will not proceed further, try to find next value of goal.
3. N==3(12%3==0), so we can move further
goal = 12/3 = 4
current = 0, current+4≤ 4, ok
current = 4, current+2>4, but current = 4 so we won’t break the loop.
find next subarray.
current = 0, current +2<4, ok
current = 2, current+1 4, ok
current = 3, current+3>goal and current !=goal, therefore find next value of N
4. N == 2
goal = 12/2 = 6
current = 0, current +4 < goal, ok
current = 4, current+2 ≤goal, ok
current = 6, current +1>goal, but current == goal, so find next subarray
current = 0, current+1≤goal, ok
current = 1, current+3≤goal, ok
current = 4, current+2≤goal, ok
We have found the answer.
I would suggest you dry run this using pen and paper, you will surely get this logic. Hope I have helped you to understand this problem.
This is my first contest editorial, any improvements or suggestions are accepted :)
Happy Coding :)
