50. Pow(x, n)
in Coding Interview on Math
x의 n승(즉, x^n)을 계산하는 pow(x, n)을 구현
- convert mathmatical equation to codes
- how to do matrix multiplication using a programming language
- how we handle huge space waste when we write a program.
This would be the first follow up, What if the two input matrix are large and we can not save all of them in memory?
class Solution {
// Just simulate the process, multiply x for n times.
// T: O(n)
public double myPow(double x, int n) {
double ans = 1;
if (n < 0) {
x = 1 / x;
n = -n;
}
for (long i = 0; i < n; i++) {
ans = ans * x;
}
return ans;
}
}
class Solution {
// Fast Power Algorithm Recursive
// T: O(logn)
public double myPow(double x, int n) {
if (n < 0) {
x = 1 / x;
n = -n;
}
return fastPow(x, n);
}
private double fastPow(double x, int n) {
if (n == 0) {
return 1.0;
}
double half = fastPow(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}
}
