[LeetCode][29. Divide Two Integers] 5 Approaches: Brute Force use Long, Brute Force use Int, Binary Search use Long, Binary Search use Int and Recursion
By Long Luo
This article is the solution 5 Approaches: BF use Long, BF use Int, Binary Search use Long, Binary Search use Int and Recursion of Problem 29. Divide Two Integers , Chinese version is 3种方法:暴力法,二分搜索,递归 .
Here shows 5 Approaches to slove this problem: Brute Force use \(\texttt{Long}\), Brute Force use \(\texttt{Int}\), Binary Search use \(\texttt{Long}\), Binary Search use \(\texttt{Int}\) and Recursion.
Intuition
To divide two integers without using multiplication, division, and mod operator, so we can subtract the \(\textit{divisor}\) from the \(\textit{dividend}\) util the \(\textit{result} \ge 0\).
Brute Force use Long
We can make the \(\textit{dividend}\) and \(\textit{divisor}\) positive, and cast to \(\texttt{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
30public 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
44public 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)\).
- Space Complexity: \(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
45class 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)\).
- Space Complexity: \(O(1)\).
Binary Search use Long
Refer to Fast Power Algorithm: Binary Exponentiation , we can use the \(\texttt{quickAdd}\) like the \(\texttt{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
54class 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 \times logy)\).
- Space Complexity: \(O(1)\).
Binary Search use Int
- the corner cases;
- Record the sign of the final result and turn both numbers to negative numbers;
- Approximate the \(\textit{divisor}\) by increasing the \(\textit{dividend}\) incrementally.
1 | class Solution { |
Analysis
- Time Complexity: \(O(logx \times logy)\).
- Space Complexity: \(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
53class 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 \times logy)\).
- Space Complexity: \(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. 😉😃💗