Any problem with the test case?


  • 0
    D

    Because I have tested my code locally, and it is correct.

    /* The guess API is defined in the parent class GuessGame.
       @param num, your guess
       @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
          int guess(int num); */
    class GuessGame {
        public int guess(int num) {
            if (num == g) {
                return 0;
            } else if (num > g) {
                return 1;
            } else {
                return -1;
            }
        }
        public GuessGame(int g) {
            this.g = g;
        }
        int g;
    }
    
    public class Solution extends GuessGame {
        public static void main(String[] args) {
            Solution s = new Solution(3);
            System.out.println(s.guessNumber(10));
        }
    
        public Solution(int g) {
            super(g);
        }
    
        public int guessNumber(int n) {
            return guessNumber(1, n);
        }
    
        private int guessNumber(int s, int e) {
            if (s == e) {
                return s;
            }
            int mid = s + (e - s) / 2;
            int result = guess(mid);
            if (result == 0) {
                return mid;
            } else if (result > 0) {
                return guessNumber(s, mid);
            } else {
                return guessNumber(mid + 1, e);
            }
        }
    }
    

  • 0
    X

    Used binary search and test locally, it is working, but it keeps saying "Time Limit Exceeded" after Run Code in LeetCode


  • 1
    M

    I was getting the "Time Limit Exceeded" issue as well. I changed how I calculated the midpoint, and that made my solution pass the test cases. It makes no sense tho as the original midpoint calculation is accurate and should require less cpu cycles.

     public int guessNumber(int n) {
            
            int low = 1,
                high = n,
                mid = 0;
                
            while (low <= high) {
                // mid = (high + low) / 2;  // this causes the "Time Limit Exceeded" failure.
                mid = low + (high - low) / 2;
                int result = guess(mid);
                if ( result == 0 ) {
                    return mid;
                } else if ( result == -1 ) {
                    high = mid - 1; // search bottom half.
                } else {
                    low = mid + 1;  // search upper half.
                }
            }
            return -1;
        }
    

  • 0
    D

    It looks like I have understood the question in an opposite way. When guess function returns -1, it means the system's hidden number is smaller. Hope this help you guys!


  • 0
    M

    I understand the question. I just returned -1; in the case that the number wasn't ever found (maybe the guess(...) function is has a bug in it in the real world or something). It shouldn't happen, but might as well return -1 to notify the API consumer that the number couldn't be guessed correctly.

    The solution I pasted was accepted by leetcode. My issue was that the line I commented out was unaccepted by leetcode because of a "Time Limit Exceeded" error.

    mid = (high + low) / 2;
    mid = low + (high - low) / 2;

    both of those equations will evaluate to the same value, but only the 2nd one passes the test cases.

    By the way, you're solution isn't passing probably because it will cause a stackoverflow error on large numbers. An iterative solution is the right approach here.


  • 0
    D

    @michael161 Very good personal example to tell us why we really need s + (e - s) / 2


  • 0
    J

    @michael161 I met exactly the same problem as well.


  • 0
    M

    So the reason why we need to do s + (e - s) /2 is because (s + e) /2 can cause an integer overflow error when the operation s + e is performed.


  • 0
    Z

    Hi,
    I think if use mid =(high + low) / 2, it may cause overflow (> INT_MAX)
    but if use low +(high - low)/2, there will not be this problem.


  • 0
    L

    For the benefit of anyone who wants to learn more about int mid =(low + high) / 2; vs. int mid = low + ((high - low) / 2);, here is a good article by google.


Log in to reply
 

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