0

Leetcode problem: valid perfect square

My answer is:

public class Solution {
    public boolean isPerfectSquare(int num) {
        int l = 0;
        int r = (num>>1)+1;
        while(l<=r) {
            int mid = (l+r)>>1;
            long temp = mid*mid;// why long
            if( temp == num) return true;
            else if( temp< num) l = mid+1;
            else r=mid-1;
        }
        return false;
    }
}

This answer time limit exceeds (when input 2^31-1). but if I changed l,r,mid to long (not int), it works. Why? Thanks

Community
  • 1
  • 1
BAE
  • 8,550
  • 22
  • 88
  • 171
  • see http://stackoverflow.com/questions/271076/what-is-the-difference-between-an-int-and-a-long-in-c – Lior Kogan Jun 26 '16 at 16:04
  • 3
    To elaborate, not only has `temp` to be capable of holding all possible results, but `mid*mid` has to be evaluated accordingly - `mid*(long)mid` should do. Do _not_ guess which of numerous variants is faster. Don't even _think_ there should be _fastest_. – greybeard Jun 26 '16 at 16:12
  • Language tag is important here. – MBo Jun 26 '16 at 16:48
  • Also: https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html?m=1 – fgb Jun 26 '16 at 19:54

1 Answers1

2

If you debug your code, you can see what is going wrong. One way to "debug" is to insert print statements, so insert the following code right after the temp assignment:

System.out.printf("l=%1$08x=%1$-10d r=%2$08x=%2$-10d mid=%3$08x=%3$-10d temp=%4$016x=%4$d%n", l, r, mid, temp);
if (temp < 0)
    throw new IllegalStateException();

This will print the 4 values l, r, mid, and temp in both hex and decimal, aligned for easy comparison. The if statement is inserted to end the loop when an obvious internal error has occurred, and it will fire.

Output when calling isPerfectSquare(Integer.MAX_VALUE):

l=00000000=0          r=40000000=1073741824 mid=20000000=536870912  temp=0000000000000000=0
l=20000001=536870913  r=40000000=1073741824 mid=30000000=805306368  temp=0000000000000000=0
l=30000001=805306369  r=40000000=1073741824 mid=38000000=939524096  temp=0000000000000000=0
l=38000001=939524097  r=40000000=1073741824 mid=3c000000=1006632960 temp=0000000000000000=0
l=3c000001=1006632961 r=40000000=1073741824 mid=3e000000=1040187392 temp=0000000000000000=0
l=3e000001=1040187393 r=40000000=1073741824 mid=3f000000=1056964608 temp=0000000000000000=0
l=3f000001=1056964609 r=40000000=1073741824 mid=3f800000=1065353216 temp=0000000000000000=0
l=3f800001=1065353217 r=40000000=1073741824 mid=3fc00000=1069547520 temp=0000000000000000=0
l=3fc00001=1069547521 r=40000000=1073741824 mid=3fe00000=1071644672 temp=0000000000000000=0
l=3fe00001=1071644673 r=40000000=1073741824 mid=3ff00000=1072693248 temp=0000000000000000=0
l=3ff00001=1072693249 r=40000000=1073741824 mid=3ff80000=1073217536 temp=0000000000000000=0
l=3ff80001=1073217537 r=40000000=1073741824 mid=3ffc0000=1073479680 temp=0000000000000000=0
l=3ffc0001=1073479681 r=40000000=1073741824 mid=3ffe0000=1073610752 temp=0000000000000000=0
l=3ffe0001=1073610753 r=40000000=1073741824 mid=3fff0000=1073676288 temp=0000000000000000=0
l=3fff0001=1073676289 r=40000000=1073741824 mid=3fff8000=1073709056 temp=0000000040000000=1073741824
l=3fff8001=1073709057 r=40000000=1073741824 mid=3fffc000=1073725440 temp=0000000010000000=268435456
l=3fffc001=1073725441 r=40000000=1073741824 mid=3fffe000=1073733632 temp=0000000004000000=67108864
l=3fffe001=1073733633 r=40000000=1073741824 mid=3ffff000=1073737728 temp=0000000001000000=16777216
l=3ffff001=1073737729 r=40000000=1073741824 mid=3ffff800=1073739776 temp=0000000000400000=4194304
l=3ffff801=1073739777 r=40000000=1073741824 mid=3ffffc00=1073740800 temp=0000000000100000=1048576
l=3ffffc01=1073740801 r=40000000=1073741824 mid=3ffffe00=1073741312 temp=0000000000040000=262144
l=3ffffe01=1073741313 r=40000000=1073741824 mid=3fffff00=1073741568 temp=0000000000010000=65536
l=3fffff01=1073741569 r=40000000=1073741824 mid=3fffff80=1073741696 temp=0000000000004000=16384
l=3fffff81=1073741697 r=40000000=1073741824 mid=3fffffc0=1073741760 temp=0000000000001000=4096
l=3fffffc1=1073741761 r=40000000=1073741824 mid=3fffffe0=1073741792 temp=0000000000000400=1024
l=3fffffe1=1073741793 r=40000000=1073741824 mid=3ffffff0=1073741808 temp=0000000000000100=256
l=3ffffff1=1073741809 r=40000000=1073741824 mid=3ffffff8=1073741816 temp=0000000000000040=64
l=3ffffff9=1073741817 r=40000000=1073741824 mid=3ffffffc=1073741820 temp=0000000000000010=16
l=3ffffffd=1073741821 r=40000000=1073741824 mid=3ffffffe=1073741822 temp=0000000000000004=4
l=3fffffff=1073741823 r=40000000=1073741824 mid=3fffffff=1073741823 temp=ffffffff80000001=-2147483647
Exception in thread "main" java.lang.IllegalStateException
    at Test.isPerfectSquare(Test.java:14)
    at Test.main(Test.java:4)

As you can see, your problem occurs already in the first iteration, where temp is calculated to 0.

That is caused by the numeric overflow when squaring 0x2000_0000. It should be 0x0400_0000_0000_0000 but it is 0 because the multiplication is done using int math.

Change to long math by casting at least one of them to long, e.g. change line to long temp = (long)mid * mid;.

With that change, your debug output becomes:

l=00000000=0          r=40000000=1073741824 mid=20000000=536870912  temp=0400000000000000=288230376151711744
l=00000000=0          r=1fffffff=536870911  mid=0fffffff=268435455  temp=00ffffffe0000001=72057593501057025
l=00000000=0          r=0ffffffe=268435454  mid=07ffffff=134217727  temp=003ffffff0000001=18014398241046529
l=00000000=0          r=07fffffe=134217726  mid=03ffffff=67108863   temp=000ffffff8000001=4503599493152769
l=00000000=0          r=03fffffe=67108862   mid=01ffffff=33554431   temp=0003fffffc000001=1125899839733761
l=00000000=0          r=01fffffe=33554430   mid=00ffffff=16777215   temp=0000fffffe000001=281474943156225
l=00000000=0          r=00fffffe=16777214   mid=007fffff=8388607    temp=00003fffff000001=70368727400449
l=00000000=0          r=007ffffe=8388606    mid=003fffff=4194303    temp=00000fffff800001=17592177655809
l=00000000=0          r=003ffffe=4194302    mid=001fffff=2097151    temp=000003ffffc00001=4398042316801
l=00000000=0          r=001ffffe=2097150    mid=000fffff=1048575    temp=000000ffffe00001=1099509530625
l=00000000=0          r=000ffffe=1048574    mid=0007ffff=524287     temp=0000003ffff00001=274876858369
l=00000000=0          r=0007fffe=524286     mid=0003ffff=262143     temp=0000000ffff80001=68718952449
l=00000000=0          r=0003fffe=262142     mid=0001ffff=131071     temp=00000003fffc0001=17179607041
l=00000000=0          r=0001fffe=131070     mid=0000ffff=65535      temp=00000000fffe0001=4294836225
l=00000000=0          r=0000fffe=65534      mid=00007fff=32767      temp=000000003fff0001=1073676289
l=00008000=32768      r=0000fffe=65534      mid=0000bfff=49151      temp=000000008ffe8001=2415820801
l=00008000=32768      r=0000bffe=49150      mid=00009fff=40959      temp=0000000063fec001=1677639681
l=0000a000=40960      r=0000bffe=49150      mid=0000afff=45055      temp=0000000078fea001=2029953025
l=0000b000=45056      r=0000bffe=49150      mid=0000b7ff=47103      temp=00000000843e9001=2218692609
l=0000b000=45056      r=0000b7fe=47102      mid=0000b3ff=46079      temp=000000007e8e9801=2123274241
l=0000b400=46080      r=0000b7fe=47102      mid=0000b5ff=46591      temp=0000000081629401=2170721281
l=0000b400=46080      r=0000b5fe=46590      mid=0000b4ff=46335      temp=000000007ff79601=2146932225
l=0000b500=46336      r=0000b5fe=46590      mid=0000b57f=46463      temp=0000000080acd501=2158810369
l=0000b500=46336      r=0000b57e=46462      mid=0000b53f=46399      temp=0000000080522581=2152867201
l=0000b500=46336      r=0000b53e=46398      mid=0000b51f=46367      temp=000000008024d9c1=2149898689
l=0000b500=46336      r=0000b51e=46366      mid=0000b50f=46351      temp=00000000800e36e1=2148415201
l=0000b500=46336      r=0000b50e=46350      mid=0000b507=46343      temp=000000008002e631=2147673649
l=0000b500=46336      r=0000b506=46342      mid=0000b503=46339      temp=000000007ffd3e09=2147302921
l=0000b504=46340      r=0000b506=46342      mid=0000b505=46341      temp=0000000080001219=2147488281
l=0000b504=46340      r=0000b504=46340      mid=0000b504=46340      temp=000000007ffea810=2147395600
false
Andreas
  • 154,647
  • 11
  • 152
  • 247