## Salesforce Interview Question

Developer Program Engineers**Country:**India

**Interview Type:**Written Test

This program runs faster, and also uses DP for those who use it.

```
public class power {
int pow[];
void init(int p) {
pow = new int[p];
}
int powers(int n, int p) {
if(p==1)
return n;
if(pow[p/2]==0)
pow[p/2] = powers(n,p/2);
return pow[p/2] * pow[p/2];
}
public static void main (String args[]) {
Scanner s = new Scanner (System.in);
int n = s.nextInt(), p=s.nextInt();
power obj = new power();
obj.init(p);
System.out.println((p%2==0)?obj.powers(n,p):n*obj.powers(n,p-1));
}
}
```

```
public class Power{
public double power(int number, int n){
if(n < 0){
return 1 / powerUtil(number, n * -1);
}else if(n == 0){
return 1;
}else{
return powerUtil(number, n);
}
}
private double powerUtil(int number, int n){
if(n == 1){
return number;
}else if(n % 2 == 0){
return powerUtil(number * number, n / 2);
}else{
return number * powerUtil(number * number, n / 2);
}
}
public static void main(String[] args) {
Power p = new Power();
System.out.println(p.power(2,7));
}
}
```

you can convert n to binary and use that. it is more clear that this code runs in O(logn)

```
function pow(x, n) {
var bin = n.toString(2),
logN = Math.floor(Math.log2(n)),
pow = 1,
exp = x;
for (var i = 0; i <= logN; i++) {
if (bin[logN - i] === '1') {
pow *= exp;
}
exp *= exp;
}
return pow;
}
```

public class Main {

public static int power(int x, int n) {

if (n == 0) return 1;

else if (n == 1) return x;

else if (n % 2 == 1) {

return x * power(x, n-1);

} else {

int r = power(x, n/2);

return r * r;

}

}

public static void main(String[] args) {

int r;

r = Main.power(2,0);

System.out.println("power(2,0) = " + r);

r = Main.power(2,1);

System.out.println("power(2,1) = " + r);

r = Main.power(2,3);

System.out.println("power(2,3) = " + r);

r = Main.power(2,4);

System.out.println("power(2,4) = " + r);

}

/* (non-Java-doc)

* @see java.lang.Object#Object()

*/

public Main() {

super();

}

}

if n is even then power(x, n) = power(x, n / 2) * power(x, n / 2)

else power(x, n) = x * power(x, n - 1)

Easiest recursive implementations is

- Mike S January 17, 2015