My C++ solution runtime is 0 !


  • 0
    D
    // Forward declaration of isBadVersion API.
    bool isBadVersion(int version);
    
    class Solution { 
    public:
    int bst(long n1,long n2)
    {
        if(!isBadVersion(n2-1)&&isBadVersion(n2))return n2;
        int l=(n1+n2)/2;
        if(!isBadVersion(l)&&isBadVersion(l+1))return l+1;
        else if(isBadVersion(l))return bst(n1,l);
        else return bst(l+1,n2);
    }
    int firstBadVersion(int n) {
        if(n==0)return 0;
        return bst(1,n);
    }
    };
    

    There should be careful !
    Using int is not enough to store big number !


  • 3
    D

    There are other better solutions out there ^_^.
    for example:

    bool isBadVersion(int version);
    
    class Solution {
    public:
        int firstBadVersion(int n) {
            int start = 1;
            int end = n;
            int middle;
            while(start <= end){
                middle = ((end-start)>> 1) + start;
                if(isBadVersion(middle)) end = middle - 1;
                else start = middle + 1;
            }
            return end + 1;
        }
    };

  • 0
    D

    Can you please explain your logic?


Log in to reply
 

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