Why this one little modification can make my code unaccepted?


  • 0
    Z
        public class Solution {
            public int sqrt(int x) {
            if (x==0) 
            {
              return 0;
            }
           int begin = 1;
           int end = x;
           int result=0;
           while (begin <= end) {
              int mid = (begin+end) / 2;
              if (mid <= x/mid ) {
                   begin = mid + 1;
                   result = mid;
                    } else {
                     end = mid - 1;
              }
          }
          return result;
       }
     }
    

    This is my java code which can pass the test cases. But if I modify the "if (mid <= x/mid )" to "if (mid*mid <= x )". There will be time limit exceeded. I don't know why. Is there any difference?


  • 0
    G

    mid*mid may be a LONG value instead of a INT value.


  • 1
    B

    midmid can be overflow. For your further concern, we should use 'sub/divide' to check this kind of condition, such as if we are checking whether a10 will overflow, we can't use a*10>Integer.MAX_VALUE(which will be always false) instead of a>Integer.MAX_VALUE/10.


Log in to reply
 

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