https://leetcode.com/problems/divide-two-integers/discuss/
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
ANSWER : C++
class Solution { public: int divide(int dividend, int divisor) { if (!divisor || (dividend == INT_MIN && divisor == -1)) return INT_MAX; int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1; long long dvd = labs(dividend); long long dvs = labs(divisor); int res = 0; while (dvd >= dvs) { long long temp = dvs, multiple = 1; while (dvd >= (temp << 1)) { temp <<= 1; multiple <<= 1; } dvd -= temp; res += multiple; } return sign == 1 ? res : -res; } };
ANSWER : JAVA
https://discuss.leetcode.com/topic/23968/clean-java-solution-with-some-comment
public int divide(int dividend, int divisor) { //Reduce the problem to positive long integer to make it easier. //Use long to avoid integer overflow cases. int sign = 1; if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) sign = -1; long ldividend = Math.abs((long) dividend); long ldivisor = Math.abs((long) divisor); //Take care the edge cases. if (ldivisor == 0) return Integer.MAX_VALUE; if ((ldividend == 0) || (ldividend < ldivisor)) return 0; long lans = ldivide(ldividend, ldivisor); int ans; if (lans > Integer.MAX_VALUE){ //Handle overflow. ans = (sign == 1)? Integer.MAX_VALUE : Integer.MIN_VALUE; } else { ans = (int) (sign * lans); } return ans; } private long ldivide(long ldividend, long ldivisor) { // Recursion exit condition if (ldividend < ldivisor) return 0; // Find the largest multiple so that (divisor * multiple <= dividend), // whereas we are moving with stride 1, 2, 4, 8, 16...2^n for performance reason. // Think this as a binary search. long sum = ldivisor; long multiple = 1; while ((sum+sum) <= ldividend) { sum += sum; multiple += multiple; } //Look for additional value for the multiple from the reminder (dividend - sum) recursively. return multiple + ldivide(ldividend - sum, ldivisor); }
