What is the brute force approach and complexity for Divide Two Integers?

Subtract the divisor from the dividend until too little is left; count the subtractions with time complexity O(Q) and space complexity O(1).

What is the optimal approach and complexity for Divide Two Integers?

Double the divisor while the chunk still fits, take it away, add its count, repeat with optimal time complexity O(log² N) and space complexity O(1).

Divide Two Integers

Q: How do you identify the pattern for Divide Two Integers?

Look for key signals in the prompt: "without multiplication, division or mod" indicates Doubling (adding a number to itself) is the way to grow a chunk, and the bit-by-bit build of the answer replaces `/`.; "truncated toward zero" indicates The sign must be handled on purpose: `−7 / 2` is `−3`, not `−4`.; "clamp to the 32-bit range" indicates Only one input overflows: `INT_MIN / −1`, which must return `INT_MAX`..

Medium·LeetCode #29 Pro OnlyPattern Transfer

LeetCode

Problem Statement

Divide dividend by divisor without using multiplication, division or the mod operator. The result is truncated toward zero, so 7 / −3 is −2 and −7 / 2 is −3.

If the true quotient is bigger than 2^31 − 1, return 2^31 − 1. If it is smaller than −2^31, return −2^31.

Input

Two integers dividend and divisor, both in the 32-bit int range. divisor is never 0.

Output

The quotient, truncated toward zero and clamped to the int range.

Example 1

Input: dividend = 10, divisor = 3

Output: 3

10 / 3 is 3.33…, which truncates to 3.

Example 2

Input: dividend = 7, divisor = −3

Output: −2

7 / −3 is −2.33…, which truncates toward zero to −2.

Constraints

• −2^31 ≤ dividend, divisor ≤ 2^31 − 1
• divisor ≠ 0

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“without multiplication, division or mod”

→ Doubling (adding a number to itself) is the way to grow a chunk, and the bit-by-bit build of the answer replaces `/`.

“truncated toward zero”

→ The sign must be handled on purpose: `−7 / 2` is `−3`, not `−4`.

“clamp to the 32-bit range”

→ Only one input overflows: `INT_MIN / −1`, which must return `INT_MAX`.

Approach Complexity Ladder

Brute Force — take away one divisor at a timeO(Q)O(1)

Subtract the divisor from the dividend until too little is left; count the subtractions

Optimal — take away the biggest doubled chunkO(log² N)O(1)

Double the divisor while the chunk still fits, take it away, add its count, repeat

Brute Force Intuition

Make both numbers positive, then subtract the divisor from the dividend again and again, counting the subtractions. The count is the quotient. Add the sign at the end.

Recognition rule for this sub-pattern:

n & (n−1) removes the lowest set bit; shifts read bits one at a time.

Remember this · Bit Manipulation

Trigger

"Every element appears twice except…", power of two, counting set bits, subsets as bitmasks, O(1) space tricks.

Think

What happens to this problem if I look at each bit separately?

Key question

Which bit operation (XOR, AND, OR, shift) cancels or isolates what I need?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Bit Manipulation translate into production architectures and low-level memory mechanics.

LLD Architecture