C++ 8-line O((logN)^2) solution with overflow handling and explanation

  • 0

    The idea is to get back to the original purpose of the operation of division: n/d is to count how many d's we could find from the total n.

    Without losing generality, assuming both n > 0, d > 0.

      1. For first round, build up and check the last number in geometric sequence d, 2*d, 4*d, ... which is not exceeding n.
      1. Record the coefficient k found in Step 1 and reduce n by k*d.
      1. Repeat Steps 1 and 2 and keep building up sum of found coefficients.

    Finally, the total sum of found coefficients will be the answer. Overflow handling need to take care of when coefficient sum is reaching INT_MAX, where we need to immediately return.

        int divide(int n, int d) {
          bool negative = (n < 0)^(d < 0);
          int res = 0; long nn = abs((long)n), dd = abs((long)d);
          while (nn >= dd) {
            long x = dd, count = 1;
            while (x < nn>>1) { x<<=1; count<<=1; }
            res += count; nn -= x;
            if (res == INT_MIN) return negative? INT_MIN : INT_MAX; // overflow handling
          return negative? -res : res;

Log in to reply

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