Skip to main content

29. Divide Two Integers

medium

Divide two integers using only addition, subtraction, and bit shifts — no multiplication or division operator. A bit-shift exponential-search problem with a notorious INT_MIN overflow edge case.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Constraints

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

Examples

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Track the sign separately, then work with absolute values. Beware: |INT_MIN| overflows 32-bit. Cast to a wider type or work with negatives throughout.

Hint 2

Naive repeated subtraction is too slow when dividend is 2^31 - 1 and divisor is 1.

Hint 3

Exponential-search trick: find the largest k such that divisor << k <= dividend. Subtract divisor << k from dividend and add (1 << k) to the quotient. Repeat with the remainder.

Hint 4

Handle the only overflow case: dividend == INT_MIN and divisor == -1 — the true quotient 2^31 doesn't fit. Return INT_MAX per the spec.

Solution approach

Reveal approach

Determine the sign of the result from the input signs; record it then operate on negative magnitudes (negatives have wider range than positives in two's complement — |INT_MIN| would overflow if you flip to positive). Special-case dividend = INT_MIN, divisor = -1 -> return INT_MAX per the spec. Otherwise: while dividend (negative) <= divisor (negative), find the largest shift k such that divisor << k still >= dividend. Subtract divisor << k from dividend and add (1 << k) to the quotient. Repeat. The exponential search drops complexity from O(answer) to O((log answer)^2). Apply the saved sign and return. O(log^2 n) time, O(1) space.

Complexity

Time
O(log^2 n)
Space
O(1)

Related patterns

  • bit-manipulation
  • math
  • binary-search

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple
  • Oracle

Practice these live with InterviewChamp.AI

Drill Divide Two Integers and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →