## 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;

}