My 0ms c++ solution with O(logn) time and O(1) space


  • 4
    T
    class Solution {
    public:
        int firstBadVersion(int n) {
            int from,to,mid;
            from=1;to=n;
            while(from!=to)
            {
                mid=((long long)from+to)/2;
                if(isBadVersion(mid)==true)
                {
                    to=mid;
                }
                else
                {
                    from=mid+1;
                }
            }
            return from;
        }
    };

  • 0
    J

    why there must be a long long conversion?


  • 0
    P

    There is a hidden trap in this problem , the max positive value the type 'int' can store is 2147483647(2 ^ 32 - 1) , if there are 2147483647 versions than (1 + 2147483647) will overflow and the value wrapped to negative , so you must explicitly convert the value to the long long type to avoid the bad things happen.May these be helpful. :-D


  • 0
    L

    Without needing the conversion you can also do
    (mid = to + (from-to)/2;)


  • 0
    E
    int firstBadVersion(int n) {
        int i = (n+1)/2, l = 1, r = n;
        while(1){
            printf("%d\n",i);
            if(isBadVersion(i)){
                if(i==1||!isBadVersion(i-1)) return i;
                else{
                    r = i;
                    i  = l/2+i/2;
                }
            }else{
                l = i;
                i = i/2+r/2+1;
            }
        }
    }

  • 0
    X

    You solution is based on there must exist bad version. if all versions are not bad, your solution won't work. Example, n is 1 and 1 is good version.


Log in to reply
 

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