Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Divide Two Integers

MEDIUMProblemSolveExternal Links

Description

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

Explanation: 10 / 3 = 3.33333... which is truncated to 3. The divisor 3 fits into 10 exactly 3 times (3 × 3 = 9) with a remainder of 1.

Example 2

Input: dividend = 7, divisor = -3

Output: -2

Explanation: 7 / -3 = -2.33333... which is truncated to -2 (toward zero, not toward negative infinity). The signs are different so the result is negative.

Example 3

Input: dividend = -2147483648, divisor = -1

Output: 2147483647

Explanation: -2147483648 / -1 = 2147483648, which overflows the 32-bit signed integer range. Since 2147483648 > 2^31 - 1, we return 2^31 - 1 = 2147483647 (clamped to the maximum).

Constraints

  • −2^31 ≤ dividend, divisor ≤ 2^31 − 1
  • divisor ≠ 0

Editorial

Brute Force

Intuition

Division is fundamentally about asking: "How many times does the divisor fit into the dividend?"

Think about it like distributing candy. If you have 10 candies and want to give groups of 3 to children, you keep handing out groups of 3 until you don't have enough left. You gave out 3 groups (9 candies total) with 1 candy remaining.

So the most direct approach is: keep subtracting the divisor from the dividend, counting how many times you can do it before the dividend becomes smaller than the divisor. The count is your quotient.

Before we start subtracting, we need to handle the sign. If the dividend and divisor have different signs, the result is negative. We work with absolute values for the subtraction loop and apply the sign at the end.

Step-by-Step Explanation

Let's trace through with dividend = 10, divisor = 3:

Step 1: Determine the sign of the result.

  • Both 10 and 3 are positive → result will be positive.
  • Work with absolute values: remaining = 10, divisor = 3, quotient = 0.

Step 2: Is remaining (10) ≥ divisor (3)? Yes → subtract.

  • remaining = 10 - 3 = 7, quotient = 1

Step 3: Is remaining (7) ≥ divisor (3)? Yes → subtract.

  • remaining = 7 - 3 = 4, quotient = 2

Step 4: Is remaining (4) ≥ divisor (3)? Yes → subtract.

  • remaining = 4 - 3 = 1, quotient = 3

Step 5: Is remaining (1) ≥ divisor (3)? No → stop.

  • We cannot subtract 3 from 1 anymore.

Step 6: Return quotient = 3.

  • We subtracted 3 exactly 3 times before the remaining value (1) became smaller than the divisor.

Repeated Subtraction — Dividing 10 by 3 — Watch how we repeatedly subtract the divisor from the remaining value, counting each subtraction as one unit of the quotient.

Algorithm

  1. Handle special case: if dividend = −2^31 and divisor = −1, return 2^31 − 1 (overflow)
  2. Determine the sign of the result: negative if signs differ, positive if same
  3. Convert both dividend and divisor to their absolute values (use long to avoid overflow)
  4. Initialize quotient = 0
  5. While remaining ≥ divisor:
    • Subtract divisor from remaining
    • Increment quotient by 1
  6. Apply the sign and return the quotient

Code

#include <climits>
using namespace std;

class Solution {
public:
    int divide(int dividend, int divisor) {
        // Handle overflow: -2^31 / -1 = 2^31 which exceeds INT_MAX
        if (dividend == INT_MIN && divisor == -1)
            return INT_MAX;
        
        // Determine the sign of the result
        int sign = ((dividend > 0) ^ (divisor > 0)) ? -1 : 1;
        
        // Work with absolute values using long long to avoid overflow
        long long a = abs((long long)dividend);
        long long b = abs((long long)divisor);
        
        long long quotient = 0;
        while (a >= b) {
            a -= b;
            quotient++;
        }
        
        return (int)(sign * quotient);
    }
};
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        INT_MAX = 2**31 - 1
        INT_MIN = -(2**31)
        
        # Handle overflow case
        if dividend == INT_MIN and divisor == -1:
            return INT_MAX
        
        # Determine the sign of the result
        sign = -1 if (dividend > 0) ^ (divisor > 0) else 1
        
        # Work with absolute values
        a = abs(dividend)
        b = abs(divisor)
        
        quotient = 0
        while a >= b:
            a -= b
            quotient += 1
        
        result = sign * quotient
        return max(INT_MIN, min(INT_MAX, result))
class Solution {
    public int divide(int dividend, int divisor) {
        // Handle overflow: -2^31 / -1 exceeds Integer.MAX_VALUE
        if (dividend == Integer.MIN_VALUE && divisor == -1)
            return Integer.MAX_VALUE;
        
        // Determine the sign of the result
        int sign = ((dividend > 0) ^ (divisor > 0)) ? -1 : 1;
        
        // Work with absolute values using long to avoid overflow
        long a = Math.abs((long) dividend);
        long b = Math.abs((long) divisor);
        
        long quotient = 0;
        while (a >= b) {
            a -= b;
            quotient++;
        }
        
        return (int)(sign * quotient);
    }
}

Complexity Analysis

Time Complexity: O(dividend / divisor)

In the worst case, we subtract the divisor one at a time. If dividend = 2^31 − 1 and divisor = 1, we perform about 2.1 billion subtractions. This is far too slow — a typical time limit allows roughly 10^8 operations per second, so this would take over 20 seconds.

Space Complexity: O(1)

We use only a few variables regardless of input size.

Why This Approach Is Not Efficient

The repeated subtraction approach has a devastating worst case. Consider dividing 2,147,483,647 by 1 — we would need to subtract 1 from the dividend over 2 billion times. This is O(n) where n is the quotient, and the quotient can be as large as 2^31 − 1.

The core inefficiency: we subtract only one copy of the divisor per iteration. If the quotient is large, we waste enormous time nibbling away at the dividend one tiny piece at a time.

Key insight: what if instead of subtracting one copy of the divisor, we could subtract many copies at once? If the divisor is 3 and the remaining value is 100, why subtract 3 ninety times when we could subtract 96 (= 3 × 32) in one step? The trick is to find the largest power-of-two multiple of the divisor that fits into the remaining value, using bit shifting (which doubles a number without multiplication).

Optimal Approach - Bit Manipulation (Exponential Doubling)

Intuition

Instead of subtracting the divisor one at a time, we take the biggest possible bite each round.

Imagine you owe 100tosomeoneandcanonlypayinmultiplesof100 to someone and can only pay in multiples of 3. The brute force way is to hand over 3,thirty−threetimes.Butasmarterwayistofigureoutthelargestpower−of−twomultipleof3, thirty-three times. But a smarter way is to figure out the largest power-of-two multiple of 3 that does not exceed $100:

  • 3×1=3 × 1 = 3 ✓
  • 3×2=3 × 2 = 6 ✓
  • 3×4=3 × 4 = 12 ✓
  • 3×8=3 × 8 = 24 ✓
  • 3×16=3 × 16 = 48 ✓
  • 3×32=3 × 32 = 96 ✓
  • 3×64=3 × 64 = 192 ✗ (too much!)

So you pay 96inonego(that′s32unitsof96 in one go (that's 32 units of 3), leaving 4.Thenyourepeat:4. Then you repeat: 3 × 1 = 3fitsinto3 fits into 4, so you pay 3more(1unit),leaving3 more (1 unit), leaving 1. Total: 32 + 1 = 33 units.

The doubling is achieved via left bit shifting: x << 1 doubles x without using multiplication. We shift the divisor left repeatedly until it exceeds the remaining value, then use the last valid doubled value.

This reduces the number of outer iterations from O(quotient) to O(log quotient), since each iteration removes at least half the remaining work.

Step-by-Step Explanation

Let's trace through with dividend = 10, divisor = 3:

Step 1: Handle sign. Both positive → result is positive. Work with remaining = 10, divisor = 3, quotient = 0.

Step 2: Start outer iteration. Begin doubling the divisor:

  • chunk = 3, count = 1
  • Double: chunk = 6, count = 2. Is 6 ≤ 10? Yes, keep doubling.
  • Double: chunk = 12, count = 4. Is 12 ≤ 10? No, too big. Stop.

Step 3: Use the largest valid chunk: chunk = 6 (represents 2 copies of divisor).

  • remaining = 10 − 6 = 4
  • quotient = 0 + 2 = 2

Step 4: Start new outer iteration with remaining = 4. Begin doubling:

  • chunk = 3, count = 1
  • Double: chunk = 6, count = 2. Is 6 ≤ 4? No, too big. Stop.

Step 5: Use chunk = 3 (represents 1 copy of divisor).

  • remaining = 4 − 3 = 1
  • quotient = 2 + 1 = 3

Step 6: Check: remaining = 1 < divisor = 3? Yes → loop ends.

Step 7: Return quotient = 3.

We found the answer in just 2 outer iterations (instead of 3 with brute force). For larger inputs like 2^31 / 1, this approach uses ~31 iterations instead of 2 billion.

Exponential Doubling — Dividing 10 by 3 — Watch how we double the divisor using bit shifts to find the largest chunk that fits, then subtract it. The secondary row shows the doubling candidates being tested.

Algorithm

  1. Handle special overflow case: if dividend = −2^31 and divisor = −1, return 2^31 − 1
  2. Determine the sign: negative if exactly one of dividend/divisor is negative
  3. Convert both to absolute values (use long to safely handle −2^31)
  4. Initialize quotient = 0
  5. While remaining ≥ divisor:
    a. Set chunk = divisor, count = 1
    b. While remaining ≥ chunk × 2 (i.e., chunk << 1):
    • Double chunk: chunk = chunk << 1
    • Double count: count = count << 1
      c. Subtract chunk from remaining
      d. Add count to quotient
  6. Apply sign and return quotient (clamped to 32-bit range)

Code

#include <climits>
using namespace std;

class Solution {
public:
    int divide(int dividend, int divisor) {
        // Handle overflow: INT_MIN / -1 would exceed INT_MAX
        if (dividend == INT_MIN && divisor == -1)
            return INT_MAX;
        
        // Determine the sign of the result
        int sign = ((dividend > 0) ^ (divisor > 0)) ? -1 : 1;
        
        // Work with absolute values using long long
        long long a = abs((long long)dividend);
        long long b = abs((long long)divisor);
        
        long long quotient = 0;
        while (a >= b) {
            long long chunk = b;
            long long count = 1;
            
            // Double the chunk until it would exceed remaining
            while (a >= (chunk << 1)) {
                chunk <<= 1;
                count <<= 1;
            }
            
            // Subtract the largest chunk and accumulate count
            a -= chunk;
            quotient += count;
        }
        
        return (int)(sign * quotient);
    }
};
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        INT_MAX = 2**31 - 1
        INT_MIN = -(2**31)
        
        # Handle overflow case
        if dividend == INT_MIN and divisor == -1:
            return INT_MAX
        
        # Determine sign: negative if exactly one operand is negative
        sign = -1 if (dividend > 0) ^ (divisor > 0) else 1
        
        # Work with absolute values
        a = abs(dividend)
        b = abs(divisor)
        
        quotient = 0
        while a >= b:
            chunk = b
            count = 1
            
            # Double the chunk using bit shift until it exceeds remaining
            while a >= (chunk << 1):
                chunk <<= 1
                count <<= 1
            
            # Subtract largest chunk and accumulate
            a -= chunk
            quotient += count
        
        result = sign * quotient
        return max(INT_MIN, min(INT_MAX, result))
class Solution {
    public int divide(int dividend, int divisor) {
        // Handle overflow: Integer.MIN_VALUE / -1 exceeds Integer.MAX_VALUE
        if (dividend == Integer.MIN_VALUE && divisor == -1)
            return Integer.MAX_VALUE;
        
        // Determine the sign of the result
        int sign = ((dividend > 0) ^ (divisor > 0)) ? -1 : 1;
        
        // Work with absolute values using long
        long a = Math.abs((long) dividend);
        long b = Math.abs((long) divisor);
        
        long quotient = 0;
        while (a >= b) {
            long chunk = b;
            long count = 1;
            
            // Double the chunk until it would exceed remaining
            while (a >= (chunk << 1)) {
                chunk <<= 1;
                count <<= 1;
            }
            
            // Subtract the largest chunk and accumulate count
            a -= chunk;
            quotient += count;
        }
        
        return (int)(sign * quotient);
    }
}

Complexity Analysis

Time Complexity: O(log²(dividend))

The outer loop runs at most O(log(dividend / divisor)) times because each iteration removes at least divisor from the remaining value, and the doubling ensures we remove a power-of-two multiple. The inner doubling loop runs at most O(log(dividend / divisor)) times per outer iteration since we double until we exceed the remaining value.

In practice, for 32-bit integers, the outer loop runs at most 31 times and the inner loop runs at most 31 times, giving an upper bound of about 31 × 31 ≈ 961 operations — effectively constant time for fixed-width integers.

Space Complexity: O(1)

We use only a few variables (chunk, count, quotient, sign). No additional data structures are needed, and space does not grow with input size.