Solution using std::partition_point


  • 0
    G

    Well, yeah...

    // Forward declaration of isBadVersion API.
    bool isBadVersion(int version);
    
    struct number_iter {
        int val;
        bool operator ==(number_iter rhs) {
            return val == rhs.val;
        }
        bool operator !=(number_iter rhs) {
            return val != rhs.val;
        }
        number_iter& operator++() {
            ++val;
            return *this;
        }
        int operator*() {
            return val;
        }
        int operator-(number_iter rhs) {
            return val - rhs.val;
        }
        number_iter& operator+=(int x) {
            val += x;
            return *this;
        }
    };
    
    namespace std {
        template <>
        struct iterator_traits<number_iter> {
            using difference_type = int;
            using iterator_category = random_access_iterator_tag;
        };
    }
    
    class Solution {
    public:
        int firstBadVersion(int n) {
            auto it = partition_point(number_iter{0}, number_iter{n}, [](int x) { return !isBadVersion(x+1); });
            return *it + 1;
        }
    };
    

Log in to reply
 

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