[LeetCode] 50. Pow(x, n)

轉自LeetCode

Implement pow(x, n).

<Solution>

因為是 LeetCode，所以不能真的用最簡單的方式實做，必須用更有效率的方式

所以每次都將 n 除以 2 來加速 (參考資料)

而每一次把 n 除以 2，代表 x 的次方數也要乘 2

例如 : x = 3, n = 7

假設 n 已經除了兩次2，n = 7 / 2 / 2 = 1

這時候 x 等同於乘了 4 次，x = x^4 = 81

要注意的點還有次方是奇數的時候，以及次方小於 0 的時候

code 如下

	class Solution {
	public:
	double myPow(double x, int n) {
	double ans = 1.0;
	for(int i = n; i != 0; i /= 2) {
	if((i % 2) != 0) {
	//> pow is odd number
	ans *= x;
	}
	//> i is devided by 2 each iteration
	//> so pow of x need to be multiplied by 2 each iteration
	x *= x;
	}
	return (n < 0) ? 1.0 / ans : ans;
	}
	};

view raw pow.cpp hosted with ❤ by GitHub