Interview Classic 150 Questions P50 Pow(x, n)

---

Timeline

Timeline

2025-11-26

init

Math

---

Problem:

If we directly loopntimes, the time isO(n), it will time out. Use fast exponentiation:

Fast exponentiation is based on a fact:

• If n is even:

  $$x^n = (x^2)^{n/2}$$

• If n is odd:

  $$x^n = x \cdot x^{n-1}$$

Each time n is halved, so the time complexity isO(log n)。

class Solution {
    public:
	double myPow(double x, int n)
	{
		// Fast exponentiation
		long pow = (long)n;
		if (pow < 0) {
			x = 1 / x;
			pow = -pow;
		}

		double res = 1;
		while (pow > 0) {
			if ((pow & 0x1) == 0) {
				x = x * x;
				pow = pow / 2;
			} else {
				res *= x;
				pow = pow - 1;
			}
		}
		return res;
	}
};