# How did author came to the given conclusion?

In this question when I read the editorial, it was quite simple. But I don’t understand how did he come to this conclusion. Please explain. And what should I do, when I am not able to pick up this kind of thing in a contest? I mean if I am not understanding how he reached the conclusion, I would have never got to that conclusion myself quickly in a contest. What should I do then?

### I will share my thinking process…

I would have taken some examples and tried to make all of them equal… then I would have realized that maybe I can make at least n-1 of them equal (by taking some examples)… after that I ll take some corner cases to verify that I get at least n-1 of them equal or not
Brute force cases in my mind :-

Click to view

1)all elements equal
2)all in increasing order
3) random
all of above with size of 4-5
4) size 1
5)size 2
6) size 3

### Now by observation I will be sure that it is n-1 or n

Now I ll think that when can I make it “n”

I ll look what is similar in some examples I remember in which I can get n as answer…
Further I ll think that isn’t it dividing a value in n equal parts ? Cuz adding +1 and subtracting 1 from other won’t change the sum right… and u need max of them to be equal… so either sum is divisible by n or not… so ans is n-1 or n…

#### This is the worst case thinking process from which I can get an answer…

In best case I could have realized earlier that +1 -1 is nothing but dividing their sum in n parts as I need them to be… so that’s what experience gives…
And even this worst case thought process won’t take more than 15-20 mins…

1 Like

and

### It becomes more obvious from constraints about it is O(n) soln or O(Nlogn) or O(logn) or O(sqrtn) or O(n^2) or O(n^3)

So for example it looks O(n) then it is pretty obvious that soln would be of type I thought or hashing… if it’s O(logn) then first thing I ll think of is tree (probably segment , fenwick etc)
If Nlogn then I ll think for sorting them…
Sqrtn means sqrt decomposition…
So in this way I get a direction to think…

#### though author needs to think on his own… and he’s got experience so he can…

For example try. U ll get hint from constraints…

PSHTRG Problem - CodeChef