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
2
3
4
5
Input: dividend = 10, divisor = 3
Output: 3

Input: dividend = 7, divisor = -3
Output: -2

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int divide(int dividend, int divisor) {  
  // sign
  int sign;
  if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) {
    sign = 1;
  } else {
    sign = -1;
  }
  
  // abs
  long ldividend = Math.abs((long) dividend); // (long) is very important
  long ldivisor = Math.abs((long) divisor);
  
  // for case: -2147493848  -1
  long result = sign * divideHelper(ldividend, ldivisor);
    
  if (result > Integer.MAX_VALUE) {
    result = Integer.MAX_VALUE;
  }
  
  return (int) result;
}

Note:

  • The condition of while and the initial value of sum can be decided by some few simple cases.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// dividend  divisor  result
//      0   3   0
//      1   3   0
//      2   3   0
// 
//      3   3   1
//      4   3   1
//      5   3   1

//      6   3   2

// brute-force
private long divideHelper(long dividend, long divisor) {
  long count = 0;
  long sum = divisor;
  while (sum <= dividend) {
    count += 1;
    sum += divisor;
  }
  
  return count;
}

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

Same as the code above.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int divide(int dividend, int divisor) {  
  // sign
  int sign;
  if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) {
    sign = 1;
  } else {
    sign = -1;
  }
  
  // abs
  long ldividend = Math.abs((long) dividend); // (long) is very important
  long ldivisor = Math.abs((long) divisor);
  
  // for case: -2147493848  -1
  long result = sign * divideHelper(ldividend, ldivisor);
    
  if (result > Integer.MAX_VALUE) {
    result = Integer.MAX_VALUE;
  }
  
  return (int) result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// binary search
private long divideHelper(long dividend, long divisor) {
  long result = 0;
  
  // If the remaining dividend >= divisor, multiple could be at least 1
  while (dividend >= divisor) {
    long multiple = 1;
    long sum = divisor;
    while (sum + sum <= dividend) {
      multiple += multiple;
      sum += sum;
    }
    result += multiple;
    dividend -= sum;
  }
  
  return result;
}

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