Yatra.com Interview Question
Software Engineer / DevelopersCountry: India
Hello KK and Sanjay, I quite didn't understand the line "i*=2;" . Shouldn't it be i+=1 instead? For the given problem where x=3,y=4 the answer is (3*3*3*3=81), but the while loop breaks when x=27 as i is already 4. Am I missing something here?
can we still write more efficient algo for the case when y=2^n.
eg: y=2^13
where n=13 ~= 1101. And applying some bit arithmatic here . Interviewer give me only this much of hint . How to reach to a solution from here??
@vijay that is not right
as x<<n = (2^n) *x= y*x
But something like that i had to do during interview using bit arithmatic, but was not able to figure out exact solution there.
@ scofield , your solution is obvious , but is there any way to even reduce its time complexity.
/*Write an efficient power function.
int power (int x, int y) for calculating x^y,
especially for the case that y is of the form 2^n.*/
function pow( x, y){
/* Cases: x^0 = 1
x^1 = x
x^y = z
x^(2^n) = z
*/
if ( y < 2 ) {
var ret;
(y == 0) ? ret = 1 : ret = x;
return ret;
}
var isOdd = (y & 1);
if (!isOdd) {
return pow(x * x, y/2);
} else {
return x * pow(x * x, (y-1)/2);
}
}
- kk.nitrkl January 25, 2012