17 ms Simple JAVA Solution Beats 96.92%


  • 2
    public int firstBadVersion(int n) {
            int low = 1, high = n;
            
            while (low < high) {
                int mid = (low+high) >>> 1;
                
                if (isBadVersion(mid))
                    high = mid;
                else
                    low = mid + 1;
            }
            
            return low;
        }
    

  • 0
    N

    Could you explain why you chose to use the >>> operator over >> ? Thanks


  • 0

    @nimitha.ramesh Using >>> can avoid overflow, since it will ignore the sign bit and set it to 0. For >>, the sign bit will not be discard.


  • 0
    N

    @Import_Allen That makes sense - thanks for your response. But also when I tried to use the >> operator, my program timed out instead of giving me a wrong output. Any thoughts on that?


  • 1

    @nimitha.ramesh Let's say n = Integer.MAX_VALUE, and the expected answer is Integer.MAX_VALUE, then what will happen?

    Iteration 1: Integer.MAX_VALUE > mid > 0 and isBadVersion(mid) is false, then low = mid + 1 > 1
    Iteration 2: mid < 0 (overflow), and isBadVersion(mid) is false, then low = mid + 1 <= 0
    Iteration 3: Integer.MAX_VALUE > mid > 0, and isBadVersion(mid) is false, then low = mid + 1 > 1
    Iteration 4: mid < 0 (overflow)...

    So your program is going to loop between mid > 0 and mid < 0, and it's impossible for you to get mid = Integer.MAX_VALUE by using '>>', as a result your program will loop for ever.


Log in to reply
 

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