Description

LeetCode 29

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

  • Both dividend and divisor will be 32-bit signed integers.
  • The divisor will never be 0.
  • Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

Analysis

First, considering about the sign, we can use a variable “sign” to separate the sign from the integer. Then we must solve the overflow problem. The most reliable method is to use “long” data type. And then when the dividend is less then divisor, the result will be zero. Now we could discuss the general process. A efficient method is to use “repeated sum”, which is similar to repeated squaring in power algorithm. The time complexity and space complexity are both \(O(logn)\).

Solution

class Solution {
    public int divide(int dividend, int divisor) {
        int sign=1;
        if(dividend<0&&divisor>0||dividend>0&&divisor<0) sign=-1;
        long ldividend=Math.abs((long)dividend);
        long ldivisor=Math.abs((long)divisor);
        long res=ldivide(ldividend,ldivisor);
        if(res>Integer.MAX_VALUE)
        {
            return (sign==1)?Integer.MAX_VALUE:Integer.MIN_VALUE;
        }
        else return (int)(sign*res);
    }
    public long ldivide(long ldividend,long ldivisor)
    {
        if(ldividend<ldivisor) return 0;
        long sum=ldivisor;
        long mul=1;
        while((sum+sum)<=ldividend)
        {
            sum=sum+sum;
            mul=mul+mul;
        }
        return mul+ldivide(ldividend-sum,ldivisor);
    }
}

Tip

Look at the line 15, what if the operator \(<=\) changes to \(<\)?

For example, the dividend is \(8\) while the divisor is \(2\).

In \(<=\) condition, after two loops the sum will equal to \(8\). And we can get the result \(4\).

However, in \(<\) condition, after two loops the program will enter into the recursive process and call \(ldivide(4, 2)\). Then after one loop it will enter into \(ldivide(2,2)\), and then \(ldivide(0,2)\). So the condition is slower than the former condition, although they have the same time complexity.

Reference

[1] https://github.com/EdwardShi92/Leetcode-Solution-Code/blob/master/DivideTwoIntegers.java

Leave a Reply

Your email address will not be published. Required fields are marked *