O(log N) C++ with long


  • 0
    D
        int divide(int dividend, int divisor) {
            if(!divisor || (dividend == INT_MIN && divisor == -1))
                return INT_MAX;
            int minus = ((dividend ^ divisor) >> 31) ? -1 : 1;
            pair<long, long> r = mdiv(labs(dividend), labs(divisor));
            return r.first * minus;
        }
        
        pair<long, long> mdiv(long de, long di) {
            if(de < di) return make_pair(0, de);
            pair<long, long> sub = mdiv(de >> 1, di);
            long f, s;
            f = (sub.first) << 1;
            s = (sub.second << 1) + (de & 1);
            if(s >= di) {
                s -= di;
                f += 1;
            }
            return make_pair(f, s);
        }
    

Log in to reply
 

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