Leetcode–Divide Two Integers

The Problem:

Divide two integers without using multiplication, division and mod operator.


  1. This is a tricky problem. Note that Integer range is MAX = 2147 483 647, MIN =- 2147 483 648, so the min number can not be processed by 0-x as common negative number, it will exceed the integer range. MIN value should be taken care of separately. Especially if the dividend is MIN, then to avoid exceeding the range, should add divisor to the dividend first and record 1 in result, then process as normal negative number.
  2. Directly use dividend-divisor will cost too much time when dividend is much larger than divisor. Since we can’t use multiplication, bit manipulation is a good alternative. Note that a<<1 is not a statement, should use a=a<<1

Java Solution

public class Solution {
    public int divide(int dividend, int divisor) {
        boolean neg = false;
        int res = 0;
        // take care of MIN
        if(divisor==Integer.MIN_VALUE && dividend==Integer.MIN_VALUE) return 1;
        if(divisor==Integer.MIN_VALUE) return 0;
        if(dividend ==Integer.MIN_VALUE){
            //---!!!---will exceed range, decrease by divisor and record 1 in result
            dividend += Math.abs(divisor);
        if(dividend < 0){
            dividend = 0-dividend;
            neg = !neg;
        if(divisor <0){
            divisor = 0-divisor;
            neg = !neg;
        int k = 0;
        while(dividend-divisor > divisor){ 
            // don't use dividend> divisor, that results in one unnecessary iteration
            divisor= divisor<<1;
            while(dividend >= divisor){
                res += 1<<k;
            divisor = divisor>>1;
            return 0-res;
        return res;

One thought on “Leetcode–Divide Two Integers

  1. Pingback: Leetcode–Sqrt(x) | Linchi is coding

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s