My solution to a “Daily Coding Problem” that I received in my mail today.
Implement integer exponentiation. That is, implement the
pow(x, y)
function, where x
and y
are integers and returns x^y
.
Do this faster than the naive method of repeated multiplication.
For example,
pow(2, 10)
should return 1024.
Here’s my solution in Typescript. I will be honest, I can’t fully visualise the iterative solution in my head. So while I solved this, not sure how will I solve the next problem that needs some bit-shifting. It’s been some time so, I need some practice with my bitwise operations
//iterartive and more efficient solution space-wise
sixtyOne(x: number, y: number) {
//function to calculate power
let res = 1;
while (y> 0) {
//if y is odd multiply,
//x with result
if((y & 1) == 1) {
res = res * x;
}
//n must be even now
y = y >> 1;
x = x * x;
}
return res;
}
//less efficient solution space-wise
sixtyOneRecursive(x: number, y: number): number {
if(y == 0) {
return 1;
} else if(y % 2 == 0) {
return this.sixtyOneRecursive(x, Math.floor(y/2)) * this.sixtyOneRecursive(x, Math.floor(y/2));
} else {
return x * this.sixtyOneRecursive(x, Math.floor(y/2)) * this.sixtyOneRecursive(x, Math.floor(y/2));
}
}
As usual, if you find any of my posts useful support me by buying or even trying one of my apps on the App Store.
Also, if you can leave a review on the App Store or Google Play Store, that would help too.
No comments:
Post a Comment