Divide Two Integers - Practice Coding Problems

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

Input & Output

Example 1 — Basic Division

$ Input: dividend = 10, divisor = 3

› Output: 3

💡 Note: 10 ÷ 3 = 3.33, truncated toward zero gives 3

Example 2 — Exact Division

$ Input: dividend = 7, divisor = -3

› Output: -2

💡 Note: 7 ÷ (-3) = -2.33, truncated toward zero gives -2

Example 3 — Overflow Case

$ Input: dividend = -2147483648, divisor = -1

› Output: 2147483647

💡 Note: Result would be 2147483648, but we cap at 2³¹-1 = 2147483647

Constraints

-2³¹ ≤ dividend, divisor ≤ 2³¹ - 1
divisor ≠ 0

Visualization

Tap to expand

Understanding the Visualization

Input

Two integers: dividend and divisor

Process

Use bit shifts to find multiples of divisor

Output

Quotient truncated toward zero

Key Takeaway

🎯 Key Insight: Use exponential search with bit shifts to find the largest multiple of divisor that fits, avoiding slow repeated subtraction

Asked in

f Facebook 45 a Amazon 38 M Microsoft 32 G Google 28

The key insight is to avoid multiplication/division/modulo by using bit shifts to exponentially increase the divisor until we find the largest multiple that fits. The optimal approach uses exponential search with bit manipulation to achieve O(log²n) time complexity instead of O(n) with repeated subtraction.

Common Approaches

Approach	Time	Space	Notes
✓ Exponential Search with Bit Shifts	O(log²(dividend))	O(1)	Use bit shifts to double the divisor and find quotient in logarithmic time
Repeated Subtraction	O(dividend/divisor)	O(1)	Subtract divisor from dividend repeatedly until remainder is smaller than divisor

Exponential Search with Bit Shifts — Algorithm Steps

Handle edge cases and determine sign
Use bit shifts to find largest multiple of divisor that fits
Subtract that multiple and repeat with remainder
Sum all the multipliers to get final quotient

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with dividend=10, divisor=3

Double Until Max

3→6, stop (12>10). Take 6 (multiple=2)

Repeat

Remainder=4, take 3 (multiple=1). Final: 2+1=3

Code -

solution.c — C

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int solution(int dividend, int divisor) {
    if (dividend == INT_MIN && divisor == -1) {
        return INT_MAX;
    }
    
    int negative = (dividend < 0) ^ (divisor < 0);
    
    long long dividendAbs = labs((long long) dividend);
    long long divisorAbs = labs((long long) divisor);
    
    long long quotient = 0;
    
    while (dividendAbs >= divisorAbs) {
        long long tempDivisor = divisorAbs;
        long long multiple = 1;
        
        while (dividendAbs >= (tempDivisor << 1)) {
            tempDivisor <<= 1;
            multiple <<= 1;
        }
        
        dividendAbs -= tempDivisor;
        quotient += multiple;
    }
    
    long long result = negative ? -quotient : quotient;
    
    if (result > INT_MAX) return INT_MAX;
    if (result < INT_MIN) return INT_MIN;
    
    return (int) result;
}

int main() {
    int dividend, divisor;
    scanf("%d", &dividend);
    scanf("%d", &divisor);
    
    int result = solution(dividend, divisor);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log²(dividend))

Outer loop runs log(dividend) times, inner loop also log(dividend) times

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables for calculations

✓ Linear Space

98.0K Views

Medium Frequency

~25 min Avg. Time

4.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Exponential Search with Bit Shifts — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler