class Solution {
public int divide(int dividend, int divisor) {
long n = Math.abs(dividend);
long d = Math.abs(divisor);
long result = 0;
while (n >= d) {
n = n - d;
result++;
}
if (dividend * divisor < 0) {
return (-1) * (int) result;
} else {
return (int) result;
}
}
}15 / 989 test cases passed.
overflow error..
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}이거만 추가ㅏ하면 overflow는 고쳐지는데
time limit이 걸리네요^^...
private static int HALF_INT_MIN = -1073741824;
public int divide(int dividend, int divisor) {
// Special case: overflow.
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
/* We need to convert both numbers to negatives.
* Also, we count the number of negatives signs. */
int negatives = 2;
if (dividend > 0) {
negatives--;
dividend = -dividend;
}
if (divisor > 0) {
negatives--;
divisor = -divisor;
}
int quotient = 0;
/* Once the divisor is bigger than the current dividend,
* we can't fit any more copies of the divisor into it. */
while (divisor >= dividend) {
/* We know it'll fit at least once as divivend >= divisor.
* Note: We use a negative powerOfTwo as it's possible we might have
* the case divide(INT_MIN, -1). */
int powerOfTwo = -1;
int value = divisor;
/* Check if double the current value is too big. If not, continue doubling.
* If it is too big, stop doubling and continue with the next step */
while (value >= HALF_INT_MIN && value + value >= dividend) {
value += value;
powerOfTwo += powerOfTwo;
}
// We have been able to subtract divisor another powerOfTwo times.
quotient += powerOfTwo;
// Remove value so far so that we can continue the process with remainder.
dividend -= value;
}
/* If there was originally one negative sign, then
* the quotient remains negative. Otherwise, switch
* it to positive. */
if (negatives != 1) {
return -quotient;
}
return quotient;
}Runtime: 1 ms, faster than 99.98% of Java online submissions for Divide Two Integers.
Memory Usage: 36.1 MB, less than 57.17% of Java online submissions for Divide Two Integers.
log^2 n
private static int HALF_INT_MIN = -1073741824;// -2**30;
public int divide(int dividend, int divisor) {
// Special case: overflow.
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
/* We need to convert both numbers to negatives.
* Also, we count the number of negatives signs. */
int negatives = 2;
if (dividend > 0) {
negatives--;
dividend = -dividend;
}
if (divisor > 0) {
negatives--;
divisor = -divisor;
}
ArrayList<Integer> doubles = new ArrayList<>();
ArrayList<Integer> powersOfTwo = new ArrayList<>();
/* Nothing too exciting here, we're just making a list of doubles of 1 and
* the divisor. This is pretty much the same as Approach 2, except we're
* actually storing the values this time. */
int powerOfTwo = -1;
while (divisor >= dividend) {
doubles.add(divisor);
powersOfTwo.add(powerOfTwo);
// Prevent needless overflows from occurring...
if (divisor < HALF_INT_MIN) {
break;
}
divisor += divisor;
powerOfTwo += powerOfTwo;
}
int quotient = 0;
/* Go from largest double to smallest, checking if the current double fits.
* into the remainder of the dividend. */
for (int i = doubles.size() - 1; i >= 0; i--) {
if (doubles.get(i) >= dividend) {
// If it does fit, add the current powerOfTwo to the quotient.
quotient += powersOfTwo.get(i);
// Update dividend to take into account the bit we've now removed.
dividend -= doubles.get(i);
}
}
/* If there was originally one negative sign, then
* the quotient remains negative. Otherwise, switch
* it to positive. */
if (negatives != 1) {
return -quotient;
}
return quotient;
}Runtime: 2 ms, faster than 34.65% of Java online submissions for Divide Two Integers.
Memory Usage: 35.7 MB, less than 97.34% of Java online submissions for Divide Two Integers.
이건 logn이라는데 왜 더 느리지???
y