Salesforce Interview Question
Developer Program EngineersCountry: 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