MediumNo. 0029

Divide Two Integers — LeetCode 29 Python Solution

Topics
Bit Manipulation, Math
Reading time
3 min

The 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.

Example

Input
dividend = 10, divisor = 3
Output
3
Explanation
10/3 = 3.33333.. which is truncated to 3.

Python solution

PythonSolution
class Solution:
    def divide(self, a: int, b: int) -> int:
        if b == 1:
            return a
        if a == -(2**31) and b == -1:
            return 2**31 - 1
        sign = (a > 0 and b > 0) or (a < 0 and b < 0)
        a = -a if a > 0 else a
        b = -b if b > 0 else b
        ans = 0
        while a <= b:
            x = b
            cnt = 1
            while x >= (-(2**30)) and a <= (x << 1):
                x <<= 1
                cnt <<= 1
            a -= x
            ans += cnt
        return ans if sign else -ans

Complexity

Time
O(log a × log b)
Space · auxiliary
O(1)

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 29. Divide Two Integers is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Bit Manipulation.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0067Add BinaryEasy
0231Power of TwoEasy
0342Power of FourEasy
0371Sum of Two IntegersMedium
0405Convert a Number to HexadecimalEasy
0477Total Hamming DistanceMedium

Frequently asked questions

How hard is LeetCode 29. Divide Two Integers?

LeetCode 29. Divide Two Integers is rated Medium on LeetCode.

What is the time complexity of LeetCode 29. Divide Two Integers?

The Python solution on this page runs in O(log a × log b).

What is the space complexity of LeetCode 29. Divide Two Integers?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 29. Divide Two Integers cover?

LeetCode 29. Divide Two Integers is tagged Bit Manipulation and Math on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.