How to deal with long overflow?


  • 5
    P

    I've been struggling with this for quite a while. I want to solve it using a binary search, and my code is quite straightforward, and I think, correct:

              if (x < 0) {
    			return -1;
              }
    		if (x == 0 || x == 1) {
    			return x;
    		}
    	    int start = 1;
    	    int end = x;
    	    while (start<=end) {
    	        int mid = start+ (end-start)/2;
    	        if (mid*mid<=x && (mid+1)*(mid+1)>x) return mid;
    	        if(mid*mid>x) {
    	            end = mid-1;
    	        } else {
    	            start = mid+1;
    	        }
    	    }
    	    return 0;
    

    Of course, it fails for 2147483647 case, because mid*mid causes integer overflow. I've tried dealing with long instead:

    long tmp = mid*mid;
    long tmp1 = (mid+1)*(mid+1)
    if (tmp<=x && tmp1>x) return mid;
    

    However, I get time limit exceeded, because even that overflows.
    How to deal with situations like this? What am I missing?


  • 2
    S

    As I know, in cpp int is same as long, what you need here is long long. I have no idea about ur time limit exceeded cause by the overflow.

    UPDATE

    I think I know your problem now.

    long tmp = mid*mid;
    long tmp1 = (mid+1)*(mid+1)
    if (tmp<=x && tmp1>x) return mid;
    

    In your code above, the mid is still int, which means mid * mid is int before the value assigns to tmp, so it will get overflow. The casting order in most language is like this. You should pay attention.


  • 1
    D
    You should use "long long".
    
    Sometimes, "long" == "long int" == "int" or "short" == "short int" == "int". It depends on the system.
    

  • 0
    P

    sorry, maybe it wasn't quite obvious, but I am using Java :)


  • 0
    G

    long long is 64 bit, but long just 32bit.


  • 1
    U

    use 'unsigned long long' which is 64-bits long.


  • 0
    P
    This post is deleted!

  • 5
    P

    for this particular question, I don't think we need to handle the overflow. Since the passing value is "int", then it must not exceed 2^32 -1, which means its sqrt won't larger than 2^16. So using binary search, using 2^16 as upper bound, will solve this OJ.


  • 0
    P

    ok, consider the following case:

    1. input x is 2^32-1
    2. upper bound for binary search is x/2 which is 2^30
    3. mid element is half of the upper bound, which is 2^29
    4. stopping condition for BS is: midmid == x
      obviously, mid
      mid will not cause only integer but long overflow as well

  • 0
    P

    no, the upper bound is 2^16, we are calculating sqrt here, so any number larger than 2^16, when you power it by 2, will exceed 2^32. this is power, not multiply :)


  • 0
    X

    In Java(I'm not familiar with cpp), the int is signed so its range is -2147483648 to 2147483647(2^31-1). Upper bound as 2^16 might not be enough because (2^16-1) still overflows.


  • 7
    B

    Hi, please avoid using "+" or "*" instead of "-" or "/".
    I modified your code a little, please see below:

    static int sqrt(int x) {
    	if (x < 0) {
    		return -1;
    	}
    	if (x == 0 || x == 1) {
    		return x;
    	}
    	int start = 1;
    	int end = x;
    	double val1,val2;
    	while (start <= end) {
    		//int mid = start + (end - start) / 2;
    		val1 = start*0.5 + end*0.5;
    		int mid = (int)val1;
    		val1 = x/mid;
    		val2 = x/(mid+1);
    		if (mid   <= val1 && (mid + 1)   > val2)
    			return mid;
    		if (mid   > val1) {
    			end = mid - 1;
    		} else {
    			start = mid + 1;
    		}
    	}
    	return 0;
    }

  • 0
    F
    This post is deleted!

  • 0
    S

    Upper bound should be sqrt(2^32-1) = sqrt(2) * 2^15, but then you should know exactly sqrt(2) (I don't think we are supposed to use Math.sqrt :))


Log in to reply
 

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