Problem: Chef and Mover(August 2017 contest problem)
This is not an editorial and I believe what I’ll say isn’t even right. I just want you to guys please read my approach to this problem and please correct me where I’m wrong since I’m not able to solve this problem. So as we know the chef can add or subtract numbers from an array’s element to the other element with the help of mover(D). Let’s jump right to my approach. First, we will take the sum of the array and after that, we will divide the sum by the size of the array which will look like this in Java
int x = sum/array.length; //if we take the sum of an array and divide it by the size, for example if we have 1 4 1 then the sum is 6 and x = 6/3 = 2 so now we know if we want each element equal all element has to be 2, end up the array as 2 2 2
now, why we need “x”? x will help us to determine is it even possible to make all the elements of an array equal. So, to check that we will check if the sum is equal to x multiply by size.
if(sum==x*size) //take same example 1 4 1 sum is 6 == 2(x)*3(size)
if the above condition is false then it is impossible to make all elements of that array equal. If the above condition is true, then we look at D. If D(the mover) is 1, then it is always possible to make all element equal no matter what. So, we will keep looping the array(try to subtract and add from elements) until all elements become x(In others words, all elements become equal). But if D is greater than 1 then we just loop the whole array(try to subtract and add from elements) once. If all the elements become equal then we return the number(answer). Otherwise, we return -1. So, the problem I found in my approach is if D is 1, and we have 10^5 elements in our array
for ex - we have 1 1 1 1 1 … 6 and size = 10^5
we will loop the above array so many times(comparing each element with the adjacent element) until we get all elements equal, and then restart from 0 to length of the array, will end up getting time limit exceed error. Please help me to solve this problem. Please help me with the right approach. I haven’t written the code yet with this approach because I was thinking looping the array so many times will give time limit exceed error. Please help!!