Reference: LeetCode

Difficulty: Medium

My Post: Brute-Force & Binary Search with Time Complexity Analysis

## 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:**

1 | Input: dividend = 10, divisor = 3 |

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

1 | public int divide(int dividend, int divisor) { |

**Note:**

- The condition of
`while`

and the initial value of`sum`

can be decided by some few simple cases.

1 | // dividend divisor result |

**Time:** $O(Q)$ where $Q$ is the `quotient`

.**Space:** $O(1)$

### Binary Search

Same as the code above.

1 | public int divide(int dividend, int divisor) { |

1 | // binary search |

**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$

- Example: $D = 48$ and $\text{divisor} = 3$, $D$ can be expressed as $2^4 \times \text{divisor}$. It means:
`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}$.

- Example: $D = 63$ and $\text{divisor} = 2$.

**Space:** $O(1)$