Skip to main content

29. Divide Two Integers

medium

Divide two integers without using multiplication, division, or mod. Use repeated subtraction with binary doubling — the bit-shift speedup that brings it to O(log n).

By Sam K., 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. 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

Naive repeated subtraction is O(n) — TLE when dividend = INT_MAX and divisor = 1.

Hint 2

Double the divisor each step (shift left by 1) to subtract chunks that are multiples of 2.

Hint 3

Track the sign separately. Convert both to positive by absolute value, but be careful about INT_MIN — its absolute value overflows 32-bit signed.

Hint 4

Work in 64-bit (long) or work with negatives so absolute-value of INT_MIN doesn't bite you.

Solution approach

Reveal approach

Sign extraction then bit-shift doubling. Determine the result sign from the XOR of the two input signs. Convert dividend and divisor to non-negative (use long or work in the negative domain to dodge INT_MIN overflow). Initialize quotient = 0. Outer loop while abs_dividend >= abs_divisor: find the largest k such that (abs_divisor << k) <= abs_dividend by doubling and counting; subtract (abs_divisor << k) from abs_dividend; add (1 << k) to the quotient. This is binary long-division — each round skims off the highest power-of-two multiple that fits. Apply the sign and clamp to the [-2^31, 2^31 - 1] range before returning. O(log n) time, O(1) space.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • bit-manipulation
  • binary-search

Related problems

Asked at

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

  • Amazon
  • Microsoft
  • Facebook

More Bit Manipulation practice problems

See all Bit Manipulation problems →