Divide Two Integers

Problem

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

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return the quotient after dividing dividend by divisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For this problem, if the quotient is strictly greater than 2^31 - 1, then return 2^31 - 1, and if the quotient is strictly less than -2^31, then return -2^31.

Examples

Example 1:

1
2
3
4
5
Input:
dividend = 10, divisor = 3
Output:
 3
Explanation: 10/3 = 3.33333.. which is truncated to 3.

Example 2:

1
2
3
4
5
Input:
dividend = 7, divisor = -3
Output:
 -2
Explanation: 7/-3 = -2.33333.. which is truncated to -2.

Solution

Method 1 — Repeated subtraction

Intuition

Repeatedly subtract divisor from dividend until what’s left is smaller than divisor. The number of subtractions is the quotient.

Approach

Handle divisor == 0 (undefined) and sign separately.
Use absolute values a = |dividend|, b = |divisor| and ans = 0.
While a >= b:
1. Subtract b from a and increment ans.
Apply sign to ans at the end and clamp to language integer limits if required.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  int divide(int dividend, int divisor) {
    if (divisor == 0) throw std::invalid_argument("divisor is zero");
    long long a = std::llabs((long long)dividend);
    long long b = std::llabs((long long)divisor);
    long long ans = 0;
    while (a >= b) {
      a -= b;
      ++ans;
    }
    int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
    return (int)(sign * ans);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
package main

import "errors"
type Solution struct{}

func (s *Solution) divide(dividend, divisor int64) (int64, error) {
  if divisor == 0 { return 0, errors.New("divisor is zero") }
  a := dividend
  if a < 0 { a = -a }
  b := divisor
  if b < 0 { b = -b }
  var ans int64
  for a >= b {
    a -= b
    ans++
  }
  if (dividend < 0) != (divisor < 0) { ans = -ans }
  return ans, nil
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public int divide(int dividend, int divisor) {
    if (divisor == 0) throw new ArithmeticException("divisor is zero");
    long a = Math.abs((long) dividend);
    long b = Math.abs((long) divisor);
    long ans = 0;
    while (a >= b) {
      a -= b;
      ++ans;
    }
    int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
    return (int) (sign * ans);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  fun divide(dividend: Int, divisor: Int): Int {
    if (divisor == 0) throw ArithmeticException("divisor is zero")
    var a = kotlin.math.abs(dividend.toLong())
    var b = kotlin.math.abs(divisor.toLong())
    var ans = 0L
    while (a >= b) {
      a -= b
      ans++
    }
    val sign = if ((dividend < 0) xor (divisor < 0)) -1 else 1
    return (sign * ans).toInt()
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def divide(self, dividend: int, divisor: int) -> int:
        if divisor == 0:
            raise ZeroDivisionError('divisor is zero')
        a = abs(dividend)
        b = abs(divisor)
        ans = 0
        while a >= b:
            a -= b
            ans += 1
        if (dividend < 0) ^ (divisor < 0):
            ans = -ans
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
pub struct Solution;
impl Solution {
  pub fn divide(&self, dividend: i64, divisor: i64) -> i64 {
    if divisor == 0 { panic!("divisor is zero") }
    let mut a = dividend.abs();
    let b = divisor.abs();
    let mut ans = 0i64;
    while a >= b {
      a -= b;
      ans += 1;
    }
    if (dividend < 0) ^ (divisor < 0) { -ans } else { ans }
  }
}

Complexity

⏰ Time complexity: O(q) where q = |dividend/divisor| — repeated subtraction requires q subtractions.
🧺 Space complexity: O(1).

Method 2 - Using Binary Shifts

We know:

1
dividend = (quotient) * divisor + remainder

We need to find the quotient given the divisor and dividend.

Any number can be represented in binary form:

1
num = a_0*2^0 + a_1*2^1 + a_2*2^2 + ... + a_n*2^n

Same goes for quotient . Let us have an example: 58/5:

58 = (11) * 5 + 3

In binary, this quotient is ( $(11)_{10} = (1011)_2$ ):

1
2
58 = (2^3 + 2^1 + 2^0) * 5 + 3                // --- (I)
58 = [(2^3 * 5) + (2^1 * 5) + (2^0 * 5)] + 3  // --- (II)

We are given the equation 58 = q * 5 + rem and need to find q.

First, multiply 5 by powers of 2 until the result exceeds the dividend. Since multiplication operator is not allowed, we use bitwise left shift for multiplication:

1
2
3
4
5
5 << 0 = 5               // less than dividend
5 << 1 = 10              // less than dividend
5 << 2 = 20              // less than dividend
5 << 3 = 40              // less than dividend
5 << 4 = 5*2*2*2*2 = 80  // exceeds divided, so stop and consider previous value

We observe that:

1
58 = (2^3 * 5) + (something * 5) + rem // --- (III)

You can see we are getting close to the equation we initialy wanted (eqa II).

Since 5 is multiplied by (2^3), we add (2^3) to our answer and update the dividend:

1
 58 - (2^3 * 5) = 18 = something * 5 + rem

Further operating on equation III:

1
2
3
4
58 - (2^3 * 5)  =  (something * 5) + rem
58 - (8 * 5) = something * 5 + rem
58 - 40 = something * 5 + rem
18 = something * 5 + rem

What we effectively have done is, subtracted the result we got from our first step from dividend (58 - 40). We arived at the same question again but with a smaller dividend this time. dividend = 18, divisor = 5

Therefore let us repeat the process:

1
2
3
5 << 0 = 5           // less than dividend
5 << 1 = 5*2 = 10    // less than dividend
5 << 2 = 5*2*2 = 20  // exceeds divided, so stop and consider previous value

We add 2^1 to our answer. Looking back:

1
2
3
18  =  (2^1 * 5) + (something * 5) + rem
58 - (2^3 * 5) = (2^1 * 5) + (something * 5) + rem
58 =  (2^3 * 5) + (2^1 * 5) + (something * 5) + rem

You can notice we are gradually advancing towards equ II: Our new dividend is now:

1
2
3
4
18 - (2^1 * 5)  =  (something * 5) + rem
18 - (2 * 5) = something * 5 + rem
18 - 10 = something * 5 + rem
8 = something * 5 + rem

dividend = 8, divisor = 5 Repeating the process:

1
2
5 << 0 = 5           // less than dividend
5 << 1 = 5*2 = 10    // exceeds divided, so stop and consider previous value

We add 2^0 to our answer. New dividend:

1
2
3
8 = (2^0 * 5) + (something * 5) + rem
8 - 5 = something * 5 + rem
3 = something * 5 + rem

dividend = 3, divisor = 5 At this step, we stop iterating as our dividend is less than the divisor (we have also found our remainder = 3, as 5 should be multiplied with 0 and what remains is the remainder).

Looking back again for the last time:

1
2
3
4
3 = 0*5 + rem
8 = (2^0 * 5) + 3
18  =  (2^0 * 5) + (2^1 * 5) + 3
58 = (2^3 * 5) + (2^1 * 5) + (2^0 * 5) + 3

In the process, we have finally reached the equation we wanted to, and have got the answer as:

1
quotient = (2^3 + 2^1 + 2^0)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <climits>
#include <cstdlib>

class Solution {
 public:
  int divide(int dividend, int divisor) {
    if (divisor == 0) return INT_MAX;
    if (divisor == -1 && dividend == INT_MIN) return INT_MAX;

    long long pDividend = std::llabs((long long)dividend);
    long long pDivisor = std::llabs((long long)divisor);

    int ans = 0;
    while (pDividend >= pDivisor) {
      int numShift = 0;
      while (pDividend >= (pDivisor << numShift)) {
        ++numShift;
      }
      ans += 1 << (numShift - 1);
      pDividend -= (pDivisor << (numShift - 1));
    }

    if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) {
      return ans;
    } else {
      return -ans;
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public int divide(int dividend, int divisor) {
    // handle special cases
    if (divisor == 0) return Integer.MAX_VALUE;
    if (divisor == -1 && dividend == Integer.MIN_VALUE) return Integer.MAX_VALUE;

    // get positive values
    long pDividend = Math.abs((long) dividend);
    long pDivisor = Math.abs((long) divisor);

    int ans = 0;
    while (pDividend >= pDivisor) {
      // calculate number of left shifts
      int numShift = 0;
      while (pDividend >= (pDivisor << numShift)) {
        numShift++;
      }

      // dividend minus the largest shifted divisor
      ans += 1 << (numShift - 1);
      pDividend -= (pDivisor << (numShift - 1));
    }

    if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) {
      return ans;
    } else {
      return -ans;
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        INT_MAX = 2**31 - 1
        INT_MIN = -2**31
        if divisor == 0:
            return INT_MAX
        if divisor == -1 and dividend == INT_MIN:
            return INT_MAX

        pDividend = abs(dividend)
        pDivisor = abs(divisor)

        ans = 0
        while pDividend >= pDivisor:
            numShift = 0
            while pDividend >= (pDivisor << numShift):
                numShift += 1

            ans += 1 << (numShift - 1)
            pDividend -= (pDivisor << (numShift - 1))

        if (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0):
            return ans
        else:
            return -ans

Complexity

⏰ Time complexity: O(log n)
🧺 Space complexity: O(1)

Problem#

Examples#

Solution#

Method 1 — Repeated subtraction#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Using Binary Shifts#

Code#

Complexity#

Problem

Examples

Solution

Method 1 — Repeated subtraction

Intuition

Approach

Code

Complexity

Method 2 - Using Binary Shifts

Code

Complexity