[LeetCode][29. Divide Two Integers] 5 Approaches: BF use Long, BF use Int, Binary Search use Long, Binary Search use Int, Recursion

By Long Luo

This article is the solution of Problem 29. Divide Two Integers , Chinese version is 3种方法:暴力法,二分搜索,递归 .

Here shows 5 Approaches to slove this problem: BF use long, BF use int, Binary Search use Long, Binary Search use Int, Recursion.

Intuition

To divide two integers without using multiplication, division, and mod operator, so we can subtract the divisor from the dividend util the result0\textit{result} \ge 0.

Brute Force use Long

We can make the dividend and divisor positive, and cast to long, then process.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int divide(int dividend, int divisor) {
if (dividend == 0) {
return 0;
}

long dividendLong = dividend;
long divisorLong = divisor;

boolean sign = false;
if (dividendLong < 0 && divisorLong < 0) {
dividendLong = -dividendLong;
divisorLong = -divisorLong;
} else if (dividendLong < 0 && divisorLong > 0) {
sign = true;
dividendLong = -dividendLong;
} else if (dividendLong > 0 && divisorLong < 0) {
sign = true;
divisorLong = -divisorLong;
}

long ans = 0;
while (dividendLong >= divisorLong) {
dividendLong -= divisorLong;
ans++;
}

ans = sign ? -ans : ans;

return ans > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) ans;
}

The solution will Time Limit Exceeded, we have to deal with some corner cases.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public int divide(int dividend, int divisor) {
if (divisor == Integer.MIN_VALUE) {
return dividend == Integer.MIN_VALUE ? 1 : 0;
}

if (dividend == Integer.MIN_VALUE) {
if (divisor == 1) {
return dividend;
} else if (divisor == -1) {
return Integer.MAX_VALUE;
}
} else if (dividend == Integer.MAX_VALUE) {
if (divisor == 1) {
return dividend;
} else if (divisor == -1) {
return -dividend;
}
}

long dividendLong = dividend;
long divisorLong = divisor;

boolean sign = false;
if (dividendLong < 0 && divisorLong < 0) {
dividendLong = -dividendLong;
divisorLong = -divisorLong;
} else if (dividendLong < 0 && divisorLong > 0) {
sign = true;
dividendLong = -dividendLong;
} else if (dividendLong > 0 && divisorLong < 0) {
sign = true;
divisorLong = -divisorLong;
}

long ans = 0;
while (dividendLong >= divisorLong) {
dividendLong -= divisorLong;
ans++;
}

ans = sign ? -ans : ans;

return ans > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) ans;
}

Analysis

  • Time Complexity: O(x/y)O(x / y).
  • Space Complexity: O(1)O(1).

Brute Force use Int

Since the environment that could only store integers within the 32-bit signed integer, so we have to deal with it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public int divide(int dividend, int divisor) {
if (divisor == Integer.MIN_VALUE) {
return dividend == Integer.MIN_VALUE ? 1 : 0;
}

if (dividend == 0) {
return 0;
}

if (dividend == Integer.MIN_VALUE) {
if (divisor == 1) {
return dividend;
} else if (divisor == -1) {
return Integer.MAX_VALUE;
}
} else if (dividend == Integer.MAX_VALUE) {
if (divisor == 1) {
return dividend;
} else if (divisor == -1) {
return -dividend;
}
}

int ans = 0;
boolean sign = true;
if (dividend > 0 && divisor > 0) {
dividend = -dividend;
sign = false;
} else if (dividend > 0 && divisor < 0) {
dividend = -dividend;
divisor = -divisor;
} else if (dividend < 0 && divisor < 0) {
sign = false;
divisor = -divisor;
}

while (dividend + divisor <= 0) {
dividend += divisor;
ans++;
}

return sign ? -ans : ans;
}
}

Analysis

  • Time Complexity: O(x/y)O(x / y).
  • Space Complexity: O(1)O(1).

Binary Search use Long

Refer to
Illustration of Fast Power Algorithm - Exponentiation by Squaring or Binary Exponentiation , we can use the quickAdd like the quickMul.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public int divide(int dividend, int divisor) {
long x = dividend;
long y = divisor;

boolean sign = false;

if ((x > 0 && y < 0) || (x < 0 && y > 0)) {
sign = true;
}

if (x < 0) {
x = -x;
}

if (y < 0) {
y = -y;
}

long left = 0;
long right = x;

while (left < right) {
long mid = (left + right + 1) >> 1;
long result = quickAdd(y, mid);
if (result <= x) {
left = mid;
} else {
right = mid - 1;
}
}

long ans = sign ? -left : left;
if (ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE) {
return Integer.MAX_VALUE;
}

return (int) ans;
}

public long quickAdd(long x, long y) {
long ans = 0;
while (y > 0) {
if ((y & 0x01) == 1) {
ans += x;
}

x += x;
y = y >> 1;
}

return ans;
}
}

Analysis

  • Time Complexity: O(logx×logy)O(logx \times logy).
  • Space Complexity: O(1)O(1).

Binary Search use Int

  1. the corner cases;
  2. Record the sign of the final result and turn both numbers to negative numbers;
  3. Approximate the divisor by increasing the dividend incrementally.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public int divide(int dividend, int divisor) {
if (divisor == Integer.MIN_VALUE) {
return dividend == Integer.MIN_VALUE ? 1 : 0;
}

if (dividend == 0) {
return 0;
}

if (dividend == Integer.MIN_VALUE) {
if (divisor == 1) {
return Integer.MIN_VALUE;
} else if (divisor == -1) {
return Integer.MAX_VALUE;
}
}

boolean sign = false;
if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
sign = true;
}

if (dividend > 0) {
dividend = -dividend;
}

if (divisor > 0) {
divisor = -divisor;
}

int MAX = Integer.MIN_VALUE >> 1;
int ans = 0;

// dividend became negative
while (dividend <= divisor) {
int temp = divisor;
int step = -1;

while (temp >= MAX && step >= MAX && temp >= dividend - temp) {
temp += temp;
step += step;
}

dividend -= temp;
ans += step;
}

return sign ? ans : -ans;
}
}

Analysis

  • Time Complexity: O(logx×logy)O(logx \times logy).
  • Space Complexity: O(1)O(1).

Recursion

The recurison method.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public int divide(int dividend, int divisor) {
if (divisor == Integer.MIN_VALUE) {
return dividend == Integer.MIN_VALUE ? 1 : 0;
}

if (dividend == 0) {
return 0;
}

if (dividend == Integer.MIN_VALUE) {
if (divisor == 1) {
return Integer.MIN_VALUE;
} else if (divisor == -1) {
return Integer.MAX_VALUE;
}
}

long x = dividend;
long y = divisor;

boolean sign = false;
if ((x > 0 && y < 0) || (x < 0 && y > 0)) {
sign = true;
}

x = x > 0 ? x : -x;
y = y > 0 ? y : -y;

long ans = div(x, y);
if (ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE) {
return Integer.MAX_VALUE;
}

return (int) (sign ? -ans : ans);
}

public long div(long dividend, long divisor) {
if (dividend < divisor) {
return 0;
}

long ans = 1;
long temp = divisor;

while ((temp + temp) <= dividend) {
ans = ans << 1;
temp = temp << 1;
}

return ans + div(dividend - temp, divisor);
}
}

Analysis

  • Time Complexity: O(logx×logy)O(logx \times logy).
  • Space Complexity: O(1)O(1).

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗