Question on sqrt(x)


  • 0
    S
    class Solution {
    public:
    int sqrt(int x) {
        if(x<=0)    // x=0
            return 0;
        if(x<4){    // x=1,2,3
            return 1;
        }
        
        int res = 2*sqrt(x/4);
        
        if((res+1)*(res+1)<=x){
            return res+1;
        }
        
        return res;
        
    }
    };
    

    Input: 2147395600

    Output: 46341

    Expected: 46340

    Why I can not pass this case?
    can any one help me?

    Thanks


  • 2
    S
    class Solution {
    public:
    int sqrt(int x) {
        if(x<=0)    // x=0
            return 0;
        if(x<4){    // x=1,2,3
            return 1;
        }
    
        int res = 2*sqrt(x/4);
    
        if(long(res+1)*(res+1)<=x){   //  Since 46341 * 46341 is greater than 2^31 - 1, it has to cast.
            return res+1;
        }
    
        return res;
    
    }
    };
    

  • 0
    S

    Thanks very much!


  • 0
    S

    Would you please explain how this recursive solution works?


Log in to reply
 

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