Interview Question
Country: United States
Power(int a, int b){
if (a==0) return 0;
int res=1;
while(b!=0){
if(b&1==1) res*=a;
a*=a;
b>>=1;}
return res;}
The interviewer is looking for a Divide&Conquer Solution
x = a.a.a.a.a.a.....(n times)
x = (a^n/2)*(a^n/2) if n is even
= (a^(n-1/2)) * (a^(n-1/2)) * a if n is off
So basically the algorithm goes like :
Problem : Calculate Power of n : Complexity T(n)
1. Divide the question in 2 halves : Complexity O(1)
2. Conquer : Multiple the halves : Complexity T(n/2)
3. Combine : Trivial : Complexity T(1)
T(n) = T(n/2) + Constant
Using Master Method, Complexity is O(log n)
Power(int a, int b){
- alex January 28, 2013if (b==0) return 1;
if (a==0) return 0;
if (b%2==0) {
return Power(a*a, b/2);
} else if (b%2==1) {
return a*Power(a*a,b/2);
}
return 0;
}