Implementation using low and high gives TLE


#1

My pseudocode looks something like this, it passes the test cases but gives TLE. I guess the complexity is O(log N) but not sure. What’s the issue here?
low = 1, high = A;
while(low<=high) int mid = (low+high)/2; if(mid*mid == A) return mid; else if(mid*mid > A) high = mid; else low = mid;
if(high - low == 1) return low;


#2

Use mid as long long , as range of A is till INT_MAX, so if mid * mid will be greater than A then it will be get overflowed.


#4

Instead of using mid*mid==A use mid==A/mid to avoid overflow.


#5

Starting mid as n/2 would help too. Dont forget to cover the corner cases and yeah like others mentioned use mid as long long.