Reference: LeetCode
Difficulty: Medium

Problem

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero.

Note:

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be $0$.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: $[−2^{31}, 2^{31} − 1]$. For the purpose of this problem, assume that your function returns $2^{31} − 1$ when the division result overflows.

Example:

Analysis

Brute-Force

Note:

• Consider the test case: -2147483648 and -1. Since the result could be 2147483648, we should use long type to store the result.

Note:

• The condition of while and the initial value of sum can be decided by some few simple cases.

Time: $O(Q)$ where $Q$ is the quotient.
Space: $O(1)$

Same as the code above.

Time: $D$ is the dividend.

• Best Case: $O(\log{D})$ when $D$ equals $(2^k \times \text{divisor})$
• Example: $D = 48$ and $\text{divisor} = 3$, $D$ can be expressed as $2^4 \times \text{divisor}$. It means:
• $3 + 3 = 6$
• $6 + 6 = 12$
• $12 + 12 = 24$
• $24 + 24 = 48$
• Worst Case: $O((\log{D})^2)$ when $D$ equals ($2^k \times \text{divisor} - 1)$
• Example: $D = 63$ and $\text{divisor} = 2$.
• After the first round, the remaining $D$ is $31$.
• And so on.
• The runtime is $O(\log{D} + \log{D/2} + \log{D/4} + \ldots + \log{1})$.
• The above runtime is upper bounded by $O(\log{D} \times \log{D})$ if we treat each term as $\log{D}$.

Space: $O(1)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.