LeetCode #29: Divide Two Integers — Solved in Java

Basic Doubling Subtraction and Bit Scan From High to Low

Image Source

Dividing two numbers without the division, multiplication, or modulus operators is a classic LeetCode problem that tests how well you can break arithmetic into its smaller building blocks. At first, it looks like a basic math problem, but the challenge comes from handling large values, negative signs, and integer overflow while keeping the logic consistent with how division actually works. Thinking of division as repeated subtraction, then realizing how to make those subtractions faster, is the main idea that guides both beginner and more optimized solutions.

When tackling this problem in Java, it helps to think less about arithmetic and more about control flow and bit operations. The goal is to express division as a series of shifts and subtractions that produce the same result without ever calling the division operator. You start by thinking about edge cases, such as when the result would overflow or when negatives are involved, and then move into how to reduce work through doubling or bit scanning. That’s the mindset that takes the solution from a naive subtraction loop to something that feels efficient and grounded in how computers actually process numbers.

LeetCode: Divide Two Integers

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

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.

Constraints:

• -231 <= dividend, divisor <= 231 - 1

• divisor != 0

Solution 1: Basic Doubling Subtraction

This method builds the quotient by taking away the largest doubled portion of the divisor that still fits into the dividend. That doubling pattern reduces the number of subtractions to roughly log₂ of the quotient, keeping the process quick.