## Adobe Interview Question

Development Support Engineers```
// forgot to login :)
double power(double x, unsigned int n)
{
if (!n) return 1.0;
if (n == 1) return x;
double result = power(x, n/2);
result *= result;
return (n&1) ? result*x : result;
}
```

The following solution computes it using floor(log(n)) multiplications.

double power(double x, unsigned int n) {

double res = 1.0;

double m = x;

if (x == 0.0)

return 0.0;

while (n) {

if (n & 1)

res *= m;

m *= m;

n >>= 1;

}

return res;

}

the guy above posted almost the same solution as mine. i believe our solution is the best in terms of the number of multiplications.

double powerofN(double num, unsigned int power)

{

double reminder=1;

if( power < 1)

return 1;

while(power > 1)

{

if(power%2 ==0 )

{

num = num * num;

power = power/2;

}

else

{

reminder = reminder * num;

num = num * num;

power = (power - 1)/2;

}

}

num = num * reminder;

// printf("The value of num is %f and result is %f\n", num, result);

return num;

}

```
#include <vector>
#include <math.h>
#include <iostream>
using namespace std;
int main(){
int x = 2;
int n = 15;
//compute pow(x,n)
//In this case the algorithm computes in atmost ceil(2 * (logn base2))+1 computations
vector <long> arr;
arr.push_back(x);
int baseComputs,numOfComputs = 0;
long result = 1;
baseComputs = floor(log2(n));
int i=1;
for (;i<=baseComputs;i++){
arr.push_back(arr[i-1]*arr[i-1]);numOfComputs++;
if(n&(1<<i-1)){
result=result*arr[i-1];numOfComputs++;
}
}
if(n&(1<<i-1)){
result=result*arr[i-1];numOfComputs++;
}
cout << "pow("<<x<<","<<n<<") is :: "<<result<<". with "<<numOfComputs<<" multiplications"<<endl;
return 1;
}
```

<pre lang="" line="1" title="CodeMonkey73107" class="run-this">public class Power {

public static int power(int base, int power) {

int res = 1;

if (power > 0) {

int mask = 0x1;

while (mask <= power) {

if ((mask & power) != 0) {

res *= base;

}

mask <<= 1;

base *= base;

}

}

return res;

}

public static void main(String[] args) {

System.out.println(Power.power(3, 6));

System.out.println(Power.power(5, 4));

System.out.println(Power.power(6, 4));

System.out.println(Power.power(10, 7));

}

}

</pre>

What are the allowed functions/operations?

- ftfish July 17, 2010You can do power with only plus (so 0 multiplication)