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 Long \texttt{Long} Long , Brute Force use Int \texttt{Int} Int , Binary Search use Long \texttt{Long} Long , Binary Search use Int \texttt{Int} Int and Recursion .
Intuition
To divide two integers without using multiplication, division, and mod operator, so we can subtract the divisor \textit{divisor} divisor from the dividend \textit{dividend} dividend util the result ≥ 0 \textit{result} \ge 0 result ≥ 0 .
Brute Force use Long
We can make the dividend \textit{dividend} dividend and divisor \textit{divisor} divisor positive, and cast to long \texttt{long} 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) O ( x / y ) .
Space Complexity : O ( 1 ) O(1) O ( 1 ) .
Brute Force use Int
Since the environment that could only store integers within the 32 − b i t 32-bit 3 2 − b i t 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) O ( x / y ) .
Space Complexity : O ( 1 ) O(1) O ( 1 ) .
Binary Search use Long
Refer to
Fast Power Algorithm: Binary Exponentiation , we can use the quickAdd \texttt{quickAdd} quickAdd like the quickMul \texttt{quickMul} 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 ( l o g x × l o g y ) O(logx \times logy) O ( l o g x × l o g y ) .
Space Complexity : O ( 1 ) O(1) 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 divisor \textit{divisor} divisor by increasing the dividend \textit{dividend} 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 ; 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 ( l o g x × l o g y ) O(logx \times logy) O ( l o g x × l o g y ) .
Space Complexity : O ( 1 ) 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 ( l o g x × l o g y ) O(logx \times logy) O ( l o g x × l o g y ) .
Space Complexity : O ( 1 ) 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 . 😉😃💗