Pow(x, n)

Intuitionwhy the exponent's binary form avoids repeated multiplication

The direct definition of x^n multiplies x by itself n times, but that repeats work unnecessarily. For example, x^8 can be formed as x, then x^2, then x^4, then x^8 by squaring each result. Every squaring doubles the exponent represented by the current base, so the useful powers grow exponentially while the number of steps grows logarithmically.

Write the exponent as a sum of powers of two. For n = 13, the binary form is 1101, so x^13 is x^8 multiplied by x^4 multiplied by x. The loop keeps a current power in x, multiplies it into the answer when the current exponent bit is 1, then squares that power and shifts the exponent right to inspect the next bit.

A negative exponent changes the value to a reciprocal: x^(-n) = (1/x)^n. Convert x to 1/x before the loop, but do not negate the original int directly. The smallest int cannot represent its own positive counterpart, so the exponent must first be widened to long long and only then negated.

Approach

1. 1Copy n into a long long named N before changing it, because negating the minimum int overflows if the operation happens while n is still an int.
2. 2For a negative N, replace x with 1 / x and replace N with -N, because the reciprocal converts a negative power into an equivalent positive power.
3. 3Initialise ans to 1.0, the multiplicative identity, so the result is already correct when the exponent is zero and every selected power can be multiplied into it.
4. 4While N is positive, inspect its lowest bit with N & 1, because that bit tells you whether the current power of x belongs in the binary decomposition of the exponent.
5. 5Multiply ans by the current x when that bit is 1, because skipping a selected binary power would remove part of the required exponent.
6. 6Square x after processing the current bit, because the next loop represents the next power of two and must use x squared rather than the current power again.
7. 7Shift N right by one bit and repeat, because this discards the bit already processed and exposes the next binary digit without scanning any exponent value more than once.
8. 8Return ans after N reaches zero, because every set bit has contributed its corresponding power and the result has been assembled without a separate pass.

Complexitythe logarithm counts exponent bits, not multiplication attempts

Annotated solutionC++ · iterative binary exponentiation · constant extra space

#include <cmath>
using namespace std;

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;

        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        double ans = 1.0;
        while (N > 0) {
            if (N & 1) {
                ans *= x;
            }
            x *= x;
            N >>= 1;
        }

        return ans;
    }
};

The order inside the loop is deliberate. The current x represents the power for the bit being inspected, so ans must use it before x is squared. After that contribution is recorded, squaring prepares x for the next bit. The long long conversion is equally important: when n is -2^31, the positive magnitude is 2^31, which an int cannot hold.

The recursive alternativethe same squaring identity with logarithmic call depth

A recursive solution can apply the identity x^n = (x^(n/2))^2 for even n, and x^n = x times x^(n-1) for odd n. It is a different arrangement of the same optimization, not a faster algorithm. It makes the mathematical structure compact, but it uses O(log(|n| + 1)) call-stack space instead of the iterative version's O(1), so the loop is the safer default.

#include <cmath>
using namespace std;

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        return power(x, N);
    }

private:
    double power(double x, long long n) {
        if (n == 0) {
            return 1.0;
        }

        double half = power(x, n / 2);
        double result = half * half;
        if (n & 1) {
            result *= x;
        }
        return result;
    }
};

Common mistakestwo wrong code shapes that look reasonable at first