# How to deal with long overflow?

• 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?

• 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.

• ``````You should use "long long".

Sometimes, "long" == "long int" == "int" or "short" == "short int" == "int". It depends on the system.
``````

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

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

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

• This post is deleted!

• 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.

• 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

• 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 :)

• 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.

• Hi, please avoid using "+" or "*" instead of "-" or "/".

``````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;
}``````

• This post is deleted!

• 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 :))

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