PPractick

The problem

A tiny microcontroller has no hardware divider, but the firmware must compute integer quotients for sensor scaling, truncated toward zero, like C++ division. Repeated subtraction is far too slow when the dividend is 2 billion and the divisor is 1. Long division in binary is fast: subtract the largest shifted copy of the divisor (divisor · 2^k) that still fits, add 2^k to the quotient, and repeat for smaller k, which is 32 steps at most. The one overflow case, INT_MIN / −1, must be clamped to INT_MAX.

Example: 10 / 3 → 3; 7 / −3 → −2.

Function signature

int divide(int dividend, int divisor);  // divisor != 0; result clamped to [INT_MIN, INT_MAX]

Test cases

Input (dividend, divisor)	Output	Explanation
(10, 3)	3	3.33 truncated
(7, -3)	-2	−2.33 truncates toward zero
(-2147483648, -1)	2147483647	2³¹ doesn't fit, so it's clamped
(-2147483648, 1)	-2147483648
(0, 5)	0
(1, 1)	1

(Confirm: no multiplication, division or modulo; shifts, addition and subtraction are fine; truncate toward zero.)

How interviewers phrase it

• "Divide two integers without using multiplication, division and mod operator" (LeetCode 29).

Clarifying questions to ask

1. Truncate toward zero or floor? (Toward zero.)
2. What about overflow? (Only INT_MIN / −1 overflows, so clamp it to INT_MAX.)
3. May I use 64-bit integers? (If not, work in negative numbers to avoid overflowing abs(INT_MIN).)

Follow-ups to expect

1. "Why not subtract the divisor repeatedly?"
2. "How does the shift method work?"
3. "How do you compare without overflowing?"
4. "How do you handle signs?"
5. "Complexity?"

Related questions

• XOR of numbers in a given range Medium
• Find missing number Easy
• Find the number that appears once, and other numbers twice Medium
• Find the repeating and missing number Medium
• Find square root of a number Medium
• Find Nth root of a number Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in