Three 4 ms C solutions using Fast Inverse Square Root , Newton's method or Binary search (beats 51.19%)


  • 2
    // Using Fast Inverse Square Root Algorithm
    int mySqrt(int x) {     
    if(x < 2) return x;
        else{
            int i;  
            float y = x;  
            float x2 = x * 0.5F;
            int res;
            i  = * ( int * ) &y;           
            i  = 0x5f3759df - ( i >> 1 ); 
            y  = * ( float * ) &i;  
            y  = y * ( 1.5F - ( x2 * y * y ) );   
            y  = y * ( 1.5F - ( x2 * y * y ) );  
            res = 1/y;
            while( res * res > x) res -= 1;
            return res; 
        }
    }
    
    // Using Newton's method
    int mySqrt(int x) {   
        if(x < 2) return x;
        else{
            int i;
            double k = x * 0.5;
            do{
                k = (k + (x / k) ) * 0.5;
            }while( k * k - x - 1  > - 10e-5);
            return (int)k;
        }
    }
    
    // Using binary search
    int mySqrt(int x) {  
        if(x < 2) return x;
        else{
            long k = x>>1;
            long product = k * k;
            long left = 0;
            long right = x;
            while(true){
                if(product > x){
                    right = k;
                }
                else if( (product + 2*k + 1) <= x ){
                    left = k;
                }
                else break;
                k = (left + right) >> 1;
                product = k * k;
            }
            return (int)k;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.