| |
GeekInterview.com > Placement Papers > Adobe > Placement Papers
| Print | |
Question: write an O(log2(N)) algorithm to find X^N
|
| May 05, 2008 05:22:00 |
#9 |
| rahuldbhagat |
Member Since: May 2008 Total Comments: 1 |
RE: write an O(log2(N)) algorithm to find X^N
|
Here is the algorithm that works well and takes O(log n) time.
Algorithm Exponientiate(x,n)
//computes x^n for an integer n>=0
{
m:= n;
power:=1;
z:=x;
while( ( m mod 2 )== 0 ) do
{
m:= m/2 ; //take the floor of the result.
z:=z^2; //square of z
}
m:=m-1;
power:=power*z;
}
return power;
} |
| |
Back To Question | |
