PRDTPAIN - Editorial

@itachikesh is correct. This is O(N^2) - it’s a simple application of a two-pointer technique O(N) for each of the N starting indices. It is certainly not greater than O(N^2 log (N)) as @amitcode1311 suggests.

1 Like

Please guys, help me.

Can someone tell me where am i going wrong in this code??
Tried finding the AM-GM using binary search.
https://www.codechef.com/viewsolution/54244899

exactly, it was inspired by the two-pointer technique.

solved problem was just of using long instead of int

Hi ,
My expectation is that you are doing wrong in searchCloser function’s first else statement where you have give a break statement let me explain why its wrong :
Consider a subarray is [1, 3, 5, 8 , 11, 13 ]

  1. l=0 , r = 5 this implies key = 7 and mid = 2
  2. As now arr[2]= 5 which is smaller than 7 so , values will change as index=2, diff = 2
    now updation of values of Binary search l = 3 and r = 5
  3. Now again 2nd iteration of while mid = 4 , arr[mid] = 11 m curr_diff = 7-11 = 4
    so now you check that as is greater than already found value of diff that is 2 you break the loop there , and print the answer considering 2 as optimal diff but hold on a second
  4. Point of problem
    take 4th value 8 = > (1-8)* (8-13)= 7 * 5 = 35
    considering your value 5=> (1-5) * (5-13) = 8 * 4= 32

I think this is the wrong, mine aproach for this question was to find the just smaller and just larger value than the key value and making answer from both of them and printing the largest one