Scale Engineer

Divide Two Integers

Med
#0029Time: O(1)Space: O(1)11 companies
Patterns
MathBit Manipulation
Companies
AdobeAmazonAppleBloomberg

Prompt

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: [−231, 231 − 1]. For this problem, if the quotient is strictly greater than 231 - 1, then return 231 - 1, and if the quotient is strictly less than -231, then return -231.

 

Example 1:

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

Example 2:

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

 

Constraints:

  • -231 <= dividend, divisor <= 231 - 1
  • divisor != 0

Approaches

3 approaches with complexity analysis and trade-offs.

This is the most efficient approach and mimics the process of long division in binary. We can determine the bits of the quotient one by one, from the most significant bit to the least significant bit. For each bit position i (from 31 down to 0), we check if the dividend is large enough to subtract the divisor shifted by i positions (divisor << i). If it is, then the i-th bit of the quotient is 1.

Algorithm

  • Handle the overflow case (Integer.MIN_VALUE / -1) and determine the sign.
  • Convert dividend and divisor to their absolute values using long.
  • Initialize a long quotient to 0.
  • Iterate a loop for i from 31 down to 0 (for each bit of the potential quotient).
  • Inside the loop, check if ldividend shifted right by i is greater than or equal to ldivisor. This is equivalent to checking ldividend >= (ldivisor << i) but avoids overflow when shifting ldivisor.
  • If the condition is true, it means the i-th bit of the quotient is 1. Add (1L << i) to the quotient and subtract (ldivisor << i) from ldividend.
  • After the loop, apply the sign to the long quotient.
  • Cast the final result to int and return.

Walkthrough

The core idea is to build the quotient bit by bit. A 32-bit integer quotient can be represented as q = b_31*2^31 + b_30*2^30 + ... + b_0*2^0, where b_i is either 0 or 1. The division equation is dividend = quotient * divisor. Substituting the binary representation of the quotient, we get dividend = (b_31*2^31 + ... + b_0*2^0) * divisor.

We can find each bit b_i starting from the most significant one, b_31. We check if dividend >= divisor * 2^i. If this condition holds, it means the i-th bit of the quotient must be 1. We then set the i-th bit in our result (quotient |= (1 << i)) and subtract divisor * 2^i from the dividend to account for this part of the quotient. We then proceed to check the next bit, i-1, with the updated, smaller dividend.

Again, we first handle signs and edge cases, using long to manage absolute values safely.

The algorithm iterates from i = 31 down to 0. In each iteration, it checks if the current ldividend is greater than or equal to ldivisor << i. A safer way to perform this check to avoid ldivisor << i from overflowing is (ldividend >> i) >= ldivisor.

If it is, we subtract ldivisor << i from ldividend and add 1L << i to our long quotient. Using 1L is important to prevent 1 << 31 from being interpreted as a negative number.

After the loop finishes, we have the absolute value of the quotient, to which we apply the sign.

class Solution {    public int divide(int dividend, int divisor) {        if (dividend == Integer.MIN_VALUE && divisor == -1) {            return Integer.MAX_VALUE;        }         int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;         long ldividend = Math.abs((long) dividend);        long ldivisor = Math.abs((long) divisor);         long quotient = 0;        for (int i = 31; i >= 0; i--) {            // Check if we can subtract (ldivisor << i) from ldividend            // This check is safer than `ldividend >= (ldivisor << i)` to avoid overflow            if ((ldividend >> i) >= ldivisor) {                // Add 2^i to the quotient                quotient += (1L << i);                // Subtract the value from the dividend                ldividend -= (ldivisor << i);            }        }         return (int) (sign * quotient);    }}

Complexity

Time

O(1)

Space

O(1)

Trade-offs

Pros

  • The most efficient solution with constant time complexity for fixed-size integers.

  • Elegant use of bit manipulation that mirrors hardware division algorithms.

Cons

  • The logic can be less intuitive than the other approaches if one is not comfortable with bitwise operations.

  • Requires careful handling of types (long) and bit shifts to avoid overflow issues.

Solutions

public class Solution {    public int Divide(int a, int b) {        if (b == 1) {            return a;        }        if (a == int.MinValue && b == -1) {            return int.MaxValue;        }        bool sign = (a > 0 && b > 0) || (a < 0 && b < 0);        a = a > 0 ? -a : a;        b = b > 0 ? -b : b;        int ans = 0;        while (a <= b) {            int x = b;            int cnt = 1;            while (x >= (int.MinValue >> 1) && a <= (x << 1)) {                x <<= 1;                cnt <<= 1;            }            ans += cnt;            a -= x;        }        return sign ? ans : -ans;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem