How to compute power(x,y) in O(1) space# JobHunting - 待字闺中
g*8
1 楼
It is easy to compute power(x,y) like this (without considering overflow and
negative number)
int power(int x, int y){
if(y==0) return 1;
if(y%2==0){
int t=power(x,y/2);
return t*t;
}
else{
int t=power(x,y-1);
return t*x;
}
}
My question is how to computer power in O(1) space because it uses recursion
, the space complexity is O(logy).
My first thought is to reduce the problem by Dynamic Programming. But dp is
notoriously bad in space complexity. But we don't want to know the
intermediate result. Any thoughts? Thank you
negative number)
int power(int x, int y){
if(y==0) return 1;
if(y%2==0){
int t=power(x,y/2);
return t*t;
}
else{
int t=power(x,y-1);
return t*x;
}
}
My question is how to computer power in O(1) space because it uses recursion
, the space complexity is O(logy).
My first thought is to reduce the problem by Dynamic Programming. But dp is
notoriously bad in space complexity. But we don't want to know the
intermediate result. Any thoughts? Thank you
