Xclusive_OR's blog

By Xclusive_OR, history, 2 months ago,

in the good function bool good(double x){ double temp=( x*x + sqrt(x) ); if(temp-c>0) return 0; else if(temp-c<=0) return 1; } why are we doing,

if(temp-c>0) return 0; else if(temp-c<=0) return 1;

instead of return temp-c== 0;

• +3

 » 2 months ago, # |   0 Because binary search is monotonic.
•  » » 2 months ago, # ^ |   +8 can u please elaborate a little more, I am having a hard time understanding why <= 0
 » 2 months ago, # |   0 If you want to check for every possible value of x then you can write return temp-c==0 in good funtion. but that method gives you tle.so for reducing time limit you need to apply here binary search and making good funtion according to bs.
 » 2 months ago, # |   0 u cant do abs(temp-c) == 0 as we r dealing with real numbers here(there is always some error in the precision of float/doubles, so comparison of 2 float/double numbers for the equality is always bit dubious, I mean this what I've learnt and experienced till now) also as pointed by rohit, temp-c == 0 gonna give u TLE.So, u can do something like abs(temp-c) <= 1e-6  double l = 0, r = 1e5; while (l < r) { double m = l + (r - l) / 2, temp = m * m - sqrt(m); if (abs(temp - c) <= 1e-6) return m; else if (temp < c) l = m; else r = m; } 
•  » » 2 months ago, # ^ |   0 or rather just go with the template of binary search for answers(involving real numbers), iterate over 100 times or so, then the same thing if the final answer is x with precision error <= 1e-6, then all the value of temp <= x, will be <= c and all the values of temp > x, will be > c. Then finally return l. This is what hv been done in the code u shared ig.