I was attempting a simple code of determining whether a number is perfect square or not and wrote the below code :
public boolean isPerfectSquare(int num) {
int l = 1;
int r = num;
while (l <= r) {
int mid = l - (l - r) / 2;
if (mid * mid == num)
return true;
else if (mid * mid < num)
l = mid + 1;
else
r = mid - 1;
}
return false;
}
While this works mostly, it doesn’t seems to work for all test cases. For example, for 808201 == 899 * 899 it returns false. However when the variables are changed from int to long it works. Why?
Advertisement
Answer
The tricky bit is mid * mid.
an int is a 32-bit number; it can therefore represent each integer starting from -2147483648 (which is -2^31) to 2147483647 (which is 2^31-1 – one less, because 0 also needs representation, of course).
That does mean that if you calculate x*x, you run into an issue. What if x*x is going to end up being more than 2147483647? Then it ‘overflows’. Which messes up your math. It’ll be more than that if x is higher than the square root of 2147483647, which is 46340. That still works. 46431 won’t. Let’s try it:
System.out.println(46340 * 46340); System.out.println(46341 * 46341);
this prints:
2147395600 -2147479015
minus? Wha?
Well, that’s that overflow thing kicking in. The real answer to 46341 * 46341 = 2147488281, but 2147488281 is not a number that an int can hold. You can try that too:
int z = 2147488281; // this is a compile-time error. try it!
When you’re using longs, the exact same rules apply, except longs are 64-bit. That means they represent from -9223372036854775808 to 9223372036854775807 (-2^63 to +2^63-1). Thus, the largest value of x, such that x*x still fits, is 3037000499. Let’s try it:
NB: in java, x * y is an expression where x and y have types. If the type of both is int, then the expression does int multiplication, and 46340 is as high as you can go before it overflows. If either x or y is long, then the other one is first upgraded to a long, and then long multiplication is done.By putting an L after a number, it has the long type, thus, in the next snippet, it’s long multiplication.
System.out.println(3037000499L * 3037000499L); System.out.println(3037000500L * 3037000500L);
prints:
9223372030926249001 -9223372036709301616
in other words, when you use longs, you can go much further, but it, too, has limits.
If you want to avoid this, you either have to avoid using any math where an intermediate result such as mid * mid can ever be larger than your inputs (so, think of a way to determine this without doing that, or think of a way to detect that overflow has occurred; if it has, you already know it couldn’t possibly work, and you can make some good guesses as to what your new value for l has to be.
That, or, use BigInteger which is limitless, at the cost of memory and speed.
NB: Don’t use l as a variable name. It looks way too much like the digit 1 🙂