Leetcode 29 Solution

This article provides solution to leetcode question 29 (divide-two-integers)
Categories:
Tags:
Access this page by simply typing in "lcs 29" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/divide-two-integers

Thinking Process

This question does not need complex algorithm design, instead, just simulate how computer divides numbers.

Time & Space Complexity

Assuming N is the bit-length of the dividend:

  • Time complexity: O(N)
  • Space complexity: O(1)

Solution

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (divisor == 0)
            return dividend > 0 ? INT_MAX : INT_MIN;



        if (dividend == INT_MIN && divisor == -1)
            return INT_MAX;



        bool sign = false;
        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0))
            sign = true;



        int64_t dividend2 = abs((int64_t)dividend);
        int64_t divisor2 = abs((int64_t)divisor);
        int64_t res = 0;



        int i = 0;
        while (dividend2 >= (divisor2 << (i + 1)))
            i++;



        while (i >= 0 && dividend2)
        {
            if (dividend2 >= (divisor2 << i))
            {
                dividend2 -= (divisor2 << i);
                res += (1 << i);
            }



            i--;
        }



        return sign ? -res : res;
    }
};