How to solve this problem?


  • 0
    D

    I haven't got any good ideas how to solve this=(

    Update1:
    Today I found very interesting blog where there is the solution of this problem with code: http://www.darrensunny.me/leetcode-divide-two-integers/

    Update2:
    This is my implementation:

    class Solution {
    public:
        int divide(int dividend, int divisor) {
            
            if (dividend == divisor) return 1;
            if (divisor == INT_MIN) return 0;
            
            int quotient = 0;
            if (dividend == INT_MIN) {
                dividend += abs(divisor);
                quotient = 1;
            }
            
            int sign = ((dividend < 0) ? -1 : 1) * ((divisor < 0) ? -1 : 1);
            dividend = abs(dividend);
            divisor = abs(divisor);
            
            int d = divisor;
            int shift = 0;
            while (divisor  <= (dividend >> (shift + 1))) shift++, divisor <<= 1;
            
            
            while (dividend >= d) {
                while (dividend < divisor) divisor >>= 1, shift--;
                quotient += 1 << shift;
                dividend -= divisor;
            }
            return quotient * sign;
        }
    };

  • 0
    S

    Diving into others post in our Discuss, you might get inspiration.

    For example, @domofeng's question and @ice4026's answer.


  • 2
    F

    Just to share my idea: to solve divide(x, y), using recursion.to solve divide(x >>1, y) and combine the results of the two halves(need to handle the remainder too). Pay attention to the sign of x and y as they can be negative.


  • 0
    2
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 0
    J

    you should add lines like here to pass INT_MIN problem:
    if (dividend == INT_MIN) {
    if(divisor == -1) //a special case need to be treat
    {
    return INT_MAX;
    }
    dividend += abs(divisor);
    quotient = 1;
    }


Log in to reply
 

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