Popular Posts

Thursday, June 30, 2011

Find XpowerY in O(logN)

It will keep on dividing the power by 2.If it is odd divide by 2 and multiply with x
public class RecursiveXpowerY {
public static void main(String[] args) {
int pow = recursiveXpowY(2, 5);
System.out.println(pow);
}
/**
* It finds the value in O(logN)
* @param x
* @param y
* @return
*/
public static int recursiveXpowY(int x, int y) {
if (x == 0)
return 1;
if (y % 2 == 1) {// y is odd
return recursiveXpowY(x * x, y / 2) * x;
} else {
return recursiveXpowY(x * x, y / 2);
}
}
}


No comments:

Post a Comment