This is O(logN) because in the while loop I double divisor each time:
divisor += divisor
Also because I double divisor every time, the values stored in "vals" are the exponentials.
This is O(logN) because in the while loop I double divisor each time:
divisor += divisor
Also because I double divisor every time, the values stored in "vals" are the exponentials.
Several of the most voted solutions have O((logN)^2) time complexity. Here I provide a faster (O(logN)) solution with the cost of O(logN) space. The idea is to store all the left shifted divisors that are less than the dividend in a list (array).
def divide(self, dividend, divisor):
"""
:type dividend: int
:type divisor: int
:rtype: int
"""
MAX_INT = 2147483647 #python 3 have removed this constant
MIN_INT = -2147483648
if (divisor == 0) or (divisor == -1 and dividend == MIN_INT):
return MAX_INT #two possible cases of overflow
vals = []
if ((dividend > 0) and (divisor > 0)) or ((dividend < 0) and (divisor < 0)):
sign = 1
else:
sign = -1
dividend = abs(dividend)
divisor = abs(divisor)
while dividend >= divisor:
vals.append(divisor)
divisor += divisor
result = 0
for i in range(len(vals) - 1, -1, -1):
if dividend >= vals[i]:
dividend -= vals[i]
result += 2**i
return result * sign
Recursive solution needs at least O(n) space
This solution optimizes the recursive call so that it has the locality advantage of dynamic programing. For exponential n, it judges whether n is even or odd. When n is even, pow(x, n) = pow(x, n/2)^2; when n is odd, pow(x, n) = pow(x, n/2)^2 * x.
public class Solution {
//[] cache;
public double pow(double x, int n) {
if(n == 0)
return 1;
boolean flag = true;
if(n < 0){
flag = false;
n = -n;
}
//cache = new double[n];
double result = dp_pow(x, n);
if(!flag){
result = 1 / result;
}
return result;
}
public double dp_pow(double x, int n){
if(n == 0)
return 1;
if(n == 1)
return x;
double result = 0;
//if(cache[n-1] != 0)
// return cache[n];
result = dp_pow(x, n/2);
result = result * result;
if(n % 2 != 0)
result = result * x;
//cache[n-1] = result;
return result;
}
}
Thanks for your answer, but the space is O(N).