</>Ali · LeetCode
#0029·MediumMath

Divide Two Integers

LeetCode #29 · Medium · Math · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Repeated Subtraction with Overflow Guards

Key insight

Division can be computed by counting how many times we can subtract the divisor from the dividend before the dividend goes negative. Promoting to long long lets us safely take absolute values (since |INT_MIN| > INT_MAX) and handle the sign at the end.

Strategy

  1. 1Short-circuit the overflow / fast-path cases involving INT_MIN and
  2. 2Determine the sign of the result from the signs of dividend and divisor.
  3. 3Work with the absolute values as long long.
  4. 4Subtract divisor from dividend until it goes negative; track how many
  5. 5Re-apply the sign to the result.
Time
O(|dividend| / |divisor|)
linear in the quotient.
Space
O(1)
Problem description(from LeetCode)

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
Input:
dividend = 10, divisor = 3
Output:
3
Example 2
Input:
dividend = 7, divisor = -3
Output:
-2

Constraints

  • •-2^31 <= dividend, divisor <= 2^31 - 1
  • •divisor != 0

C++ Solution

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

    bool negative = (dividend < 0) != (divisor < 0);
    lli result = -1;
    lli a = llabs((lli)dividend);
    lli b = llabs((lli)divisor);

    while (a >= 0) {
      a -= b;
      result++;
    }

    return negative ? -result : result;
  }
};

More Math problems