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 , Brute Force use , Binary Search use , Binary Search use and Recursion.
Intuition
To divide two integers without using multiplication, division, and mod operator, so we can subtract the from the util the .
Brute Force use Long
We can make the and positive, and cast to , then process.
JAVA
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.
JAVA
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: .
- Space Complexity: .