Wednesday, April 24, 2013

Leetcode: Divide Two Integers in C++


Divide two integers without using multiplication, division and mod operator.Solution: O(log(a/b))
unsigned int unsigndivide(unsigned int dividend, unsigned int divisor, unsigned int& mod)
    {
        if(divisor == dividend)
        {
            mod = 0;
            return 1;
        }
        else if(divisor>dividend)
        {
            mod = dividend;
            return 0;
        }
        else
        {
            unsigned int addup = divisor+divisor;
            if(dividend>=addup)
            {
                unsigned int result1 = unsigndivide(dividend, addup, mod);
                unsigned int result2 = unsigndivide(mod, divisor, mod);
                return result1+result1+result2;
            }
            else
            {
                mod = dividend - divisor;
                return 1;
            }
        }
    }
    int divide(int dividend, int divisor) {
        bool flag = false;
        if((dividend>0&&divisor<0)||(dividend<0&&divisor>0))
          flag = true;
        unsigned int abs_dividend=abs(dividend);
        unsigned int abs_divisor =abs(divisor);
        unsigned int mod =0;
        unsigned int result = unsigndivide(abs_dividend, abs_divisor, mod);
        if(flag)
        return 0-result;
        return result;
    }

No comments:

Post a Comment