Placement Papers - write an O(log2(N)) algorithm to find X^N

GeekInterview.com > Placement Papers > Adobe > Placement Papers

Go To First | Previous Question | Next Question

Placement Papers | Question 2 of 10

write an O(log2(N)) algorithm to find X^N

Total Answers and Comments: 9

Last Update: May 03, 2008 Asked by: d.sridhar85

Sponsored Links

Best Rated Answer

—

No best answer available. Please pick the good answer available or submit your answer.

April 27, 2006 15:25:06

Sameer Kumar Boxi

RE: write an O(log2(N)) algorithm to find X^N

int computeXn(int x int n)

{

if(n 2)

{

return x*x;

}

else if(n 2 0)

{

int y computeXn(x n/2);

return y*y;

}

else if(n 2 1)

{

int y computeXn(x n/2);

return y*y*x;

}

Is this answer useful? Yes | No

April 28, 2006 01:24:03

Vinay

RE: write an O(log2(N)) algorithm to find X^N

The program has a bug not all the control path returns a value

Is this answer useful? Yes | No

May 03, 2006 07:18:39

deepak kumar

RE: write an O(log2(N)) algorithm to find X^N

#include#includelong int a;long int func(long int x long int n);int s 1;void main(){ long int x n p 1; scanf( li &x); for (n 2;n<15;n++) { a x; s 1; if (n 2 1) p func(x n-1)*x; else p func(x n); printf( \n li li li x n p*s); } getch();}long int func(long int x long int n){ if (n 1) return x; if (n 2 1) {

Is this answer useful? Yes | No

May 11, 2006 07:30:59

mkag

RE: write an O(log2(N)) algorithm to find X^N

int Sq(int x int n) {

int y 0;

if (n < 0) return -1;

if (n 0) return 1;

if (n 1) return x;

if (n 2 0) {

y Sq(x n/2);

return y * y;

}

y Sq(x n/2);

return x * y * y;

}

Is this answer useful? Yes | No

May 13, 2006 00:48:14

Ashish Bhawsar

RE: write an O(log2(N)) algorithm to find X^N

long Pow(int x int n){ long Power 1 z x m n; while(m>0) { while(m 2 0) { m m/2; //Integer division z z*z; } m--; Power* z; } return Power;}

Is this answer useful? Yes | No

August 20, 2006 13:03:42

hari

RE: write an O(log2(N)) algorithm to find X^N

int xpwrn(int x int n){ if(n 1) return x ; else if(n>1) { if(n 2 0) { xpwrn(x n/2)*xpwrn(x n/2); } else { x*xpwrn(x n/2)*xpwrn(x n/2); } }}

Is this answer useful? Yes | No

August 08, 2007 20:55:28

jinhu

RE: write an O(log2(N)) algorithm to find X^N

my anwser:
int xpwrn(int x int n)
{
int i 0;
int rv 1;
int n x;
for(;i<32&&(1<<i)<x;++i)
{
if((1<<i)&x ! 0)
{
rv * n;
}
n * x;
}
return rv;
}

Is this answer useful? Yes | No

November 07, 2007 13:40:47

Sandeep Phukan

RE: write an O(log2(N)) algorithm to find X^N

class powerRecurse {

public int powerRec(int x int n){

if ( n 1 ) return x;
else {
return x*powerRec(x --n);
}

}

public static void main(String[] a){

System.out.println(new powerRecurse().powerRec(2 4));
}

}

Is this answer useful? Yes | No

May 03, 2008 05:22:00

rahuldbhagat

Member Since: May 2008 Contribution: 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;
}

Is this answer useful? Yes | No

Go To Top

User Name		Remember Me?
Password

Question Bank