Any difference between `mid * mid > x` and `x/mid < mid` ?


  • 2
    L

    I have a accepted answer and a wrong answer, the difference is so small that I don't even know why.

    accepted one:

    public class Solution {
    public int sqrt(int x) {
        if (x == 0) return 0;
        if (x < 0) return -1;
        if (x == 1) return 1;
        
        int left = 1;
        int right = x/2 + 1;
        
        while (left <= right) {
            int mid = (left + right)/2;
            
            if (mid <= x/mid && x/(mid + 1)<(mid + 1)) return mid;
            if (x/mid < mid) right = mid - 1;
            else left = mid + 1;
        }
        return 0;
    }
    

    }

    wrong one:

    public class Solution {
    public int sqrt(int x) {
        if (x == 0) return 0;
        if (x < 0) return -1;
        if (x == 1) return 1;
        
        int left = 1;
        int right = x/2 + 1;
        
        while (left <= right) {
            int mid = (left + right)/2;
            
            if (mid <= x/mid && x/(mid + 1)<(mid + 1)) return mid;
            if (mid * mid > x) right = mid - 1;
            else left = mid + 1;
        }
        return 0;
    }
    

    }

    Any difference between mid * mid > x and x/mid < mid ?


  • 5
    S

    Since mid is integer, mid * mid might overflow?


Log in to reply
 

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