Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save yitonghe00/20d426d5ecf52f63b8c576afe52555df to your computer and use it in GitHub Desktop.
Save yitonghe00/20d426d5ecf52f63b8c576afe52555df to your computer and use it in GitHub Desktop.
29. Divide Two Integers (https://leetcode.com/problems/divide-two-integers/): Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer division should truncate toward zero.
// Binary search solution
// Time: O(logn) where n is the quotient, 1ms
// Space: O(1), 33,7mb
class Solution {
public int divide(int dividend, int divisor) {
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);
long lans = ldivide(ldividend, ldivisor, sign);
if(lans > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
} else if(lans < Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
} else {
return (int)lans;
}
}
// Recursion function
private long ldivide(long ldividend, long ldivisor, int sign) {
// Base case
if(ldividend < ldivisor) {
return 0;
}
long multiple = 1;
long sum = ldivisor;
while((sum + sum) < ldividend) {
// Keep adding itself: d, d * 2, d * 4 ... until find the largest sum smaller than target
multiple += multiple;
sum += sum;
}
// Recursion calls
if(sign == 1) {
return multiple + ldivide(ldividend - sum, ldivisor, sign);
} else {
return 0 - multiple + ldivide(ldividend - sum, ldivisor, sign);
}
}
}
// Essentially the same as #1 but use bit manipulation to multiply sum by 2
// Time: O(logn)
// Space: O(1)
class Solution {
public int divide(int dividend, int divisor) {
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
boolean sign = (dividend > 0) ^ (divisor > 0);
long dvd = Math.abs((long) dividend);
long dvs = Math.abs((long) divisor);
int res = 0;
while (dvd >= dvs) {
long temp = dvs;
int multiple = 1;
while (dvd >= (temp << 1)) {
multiple <<= 1;
temp <<= 1;
}
dvd -= temp;
res += multiple;
}
return sign ? -res : res;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment