Helper comment - SQRT(N)


#1

If you are facing TLE issue - change your variables to long long.That’s it.


#2

hello
I used bunary search but still facing TLe!
I used long long as suggected by many floks, but stills getting TLE
can you please check my code :slight_smile:

int Solution::sqrt(int A) {
if (A < 0) return -1;
if( A == 0 || A == 1) return A;
long long int start = 1; long long int end = A/2;
long long int val = 0; long long int lval = 0;
while( start <= end) // A = 2 A/2 = 1 mid = 2 s = 1 e = 1 mid = 1 e = 1
{
long long int mid = start + (end - start)/2 + 1; // s = 1 e = 1
val = mid * mid;
lval =( mid -1 ) * (mid - 1);

if ( A == val) return mid;
else if( val > A  && lval < A) return mid-1;
else if ( A > val ) start = mid+1;
else end = mid;

}
return lval;
}


#3

Why are you making your answer very complicated.It could be solved very easily.Checkout my solution below and let me know if you have any doubts.

int Solution::sqrt(int A) {
    
    long low = 1;
    long high = A;
    long long result = 0;
    
    while(low <= high){
        
        long long mid = low + (high - low)/2;
        
        long long prod = mid * mid;
        
        if(prod==A){
            return mid;
        }else if(prod < A){
            low = mid;
        }else{
            high = mid-1;
        }
        
    }
    
    return (int)low;
    
}

#4

Thanks a lot for your feedback !
In fact, your solution is less complicated than mine
I submitted it on the problem page but still getting Time Limit excess as error …
Did you get the same result ?

Thanks :slight_smile:


#6

Your while loop runs infinitely because a number which is not a perfect square it checks continuously and the condition of while loop always satisfies. So check within your while loop, if a mid value gets more then one time then return the same mid value. ie store the previous mid value as mid1 and in next time if the same mid value results then return mid.


#7

Thanks! I was getting TLE and long long solved it!.
Could you tell how does using long long solve the TLE issue? I dont imagine it would run faster?

Also earlier I had calculated mid as:
int mid = low + (high-low)/2;

to avoid integer overflow;


#8

btw what is bunary search? :laughing: