Accepted with a weird BUG


  • 0
    M

    At first, my solution passed all the cases except '9'. In this case, return 2 not 3.

    Then I guess maybe the precision is too BIG, then I change precision to 1.0e-8, still one number can't pass thru which is 2147395600, return 46339 not 46340 , then I change precision to 1.0e-9, it's Accepted.

    Then I conclude that the smaller of the precision, the longer of the runtime and the more likely get the right answer.

    In order to verify my idea, I changed the precision to 1.0e-10 , however, I get the wrong answer again, sqrt(9)=2. I'm confused, thanks for any help .

    int sqrt(double x) {
        if (x ==0.0 or x == 1.0) return x;
        double precision = 1.0e-7; // 7~8WA, 9AC, 10WA, 11AC, >=12TLE.
        double start = 0.0, end = x;
        while (end-start > precision) {
            double mid = (start+end)/2;
            if (mid == x/mid) return  mid;
            else if (mid > x/mid) end = mid;
            else start = mid;
        }
        return  (start+end)/2;
    }

  • 0
    S

    Note that both the input and the output are integers, which means all the fractional digits you calculated are completely useless. Normally, people would use while (start < end) or while(start <= end) as the loop condition, depending on exactly how the loop body is implemented. These two conditions correspond to precision 1 and 0, respectively.


Log in to reply
 

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