text: Gives WA on "The king of snakes" {CodeJunk Contest}
  
  This is the question from recently CodeJunk Contest, It gives me WA , I try my best but I can’t Figure out how to correct my code.
  
  My approach->>
  Basically Using Binary search from low =1 to high=m , where m is the maximum value element in the array
  comparing the f(mid) with my global ans, and simultaneously also check for mid-1 and mid+1 half{similar that we do ne Binary search with some required modification}
  
  PS:->> I have done 2 hours on this but doesn’t reach to the solution, Please help me if you can.
  
  My solution
  
  @anon56994723
  
  @anon70990627
  
  ``````while(l<=r)
  {
  mid=(l+r)/2;
  sum1=sum(mid-1), sum2=sum(mid),sum3=sum(mid+1)
  if(sum1>sum2 && sum2<sum3) {ans=mid; break;}
  if(sum1>sum2 && sum2>sum3) l=mid+1;
  else r=mid-1;
  }
  ``````
  
  try this, it will work
  why? beacuse the function f(x) is a curve which is decreasing and then increasing
  
  Thanks Buddy!!, but can you please elaborate what is this sum function ?? , I didn’t understood this.
  
  Its not necessary to check function values of both mid-1 and mid+1.
  We know that the function attains the peak in a singular point and from that point the function value increases.So we use the same binary search to calculate the peak value by comparing the function values of mid and mid+1 alone,till the binary search auto finishes by using (l<r) case.
  The last value of mid is the answer which we computed in O(n*log n)!
  
  If stuck ---->https://pastebin.com/h7i1N6S6
  
  Happy Coding!
  
  It’s just the f(x) I think
  
  1 Like
  
  yes its f(x)
  
  I didn’t get the part where you said that it will have only one minima. Can you give me some hint regarding this?
  
  my bad…it can have 2 minima as well, but the conditions i used probably made sure we are choosing the smallest one.[ arr={1,4}, k=1, x=2,3 will give f(x) as 3]
  I believe it can be proved mathematically that minima will always lie in a range of at most 2 elements, but i didn’t try to prove it during the contest, and i didn’t think much about it later
  
  This condition is valid for any minima. So, how can we tell that it will be global minima?
  
  @sebastian There will be only two integers x1 and x2 such that f(x1 ) = f(x2 )
  
  Differentiating f(x) twice, we find that f''(x) will have only one root corresponding to a single minima/maxima. f'(x) shows that the it will be a minima.
  If x is an integer, a single value will give the minima else, two values will give the minima.
  
  Minima will always be at `sum/n`. So, it can be solved in O(n)
  https://www.codechef.com/viewsolution/35877309
  
  2 Likes