Pow(x, n)

MEDIUM✓ CHIP-TIMEDLC #50 — FULL STATEMENT ↗

The drill: Raise a real number to an integer power, positive or negative — negative exponents mean the reciprocal of the positive-power result. The trick is doing it without multiplying x by itself n separate times.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A real base value and an integer exponent arrive together, and the task is to compute the base raised to that exponent — x to the power n.

A negative exponent means the reciprocal of the positive-power result: x to the −n is defined as 1 divided by x to the n, following the exponent's magnitude and then flipping. An exponent of zero always yields 1, regardless of what the base is.

The result is a single floating-point number, and it only needs to land within a small tolerance of the true mathematical answer — this drill is really about how few multiplications the computation can get away with, not about exact floating-point bit-matching.

EX 01

x = 2 · n = 10

→ 1024

CLEAN POWER OF TWO

EX 02

x = 2 · n = -2

→ 0.25

NEGATIVE EXPONENT INVERTS

EX 03

x = 0.5 · n = 0

→ 1

ANY NONZERO BASE TO THE ZERO POWER

the exponent can be any integer, including large negative and large positive values
the base is a real number that can be negative, zero, or fractional
an exponent of zero always produces 1
results are checked against a small floating-point tolerance, not exact equality

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Multiplying x into a running total n times is correct for any n, but the exponent can be enormous — the number of multiplications needs to shrink much faster than one-per-unit-of-n.

HINT 2 THE STRUCTURE

x⁸ doesn't need seven multiplications: x² needs one, x⁴ is x² squared, x⁸ is x⁴ squared — squaring the running result doubles the exponent it represents with a single multiplication.

HINT 3 ONE STEP FROM THE ANSWER

Walk the exponent's bits: repeatedly square a running base, and whenever the current bit of n is 1, fold that squared base into the answer — this is binary (fast) exponentiation, and a negative n just means inverting x first and working with its magnitude.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE DOUBLING BASEPATTERN · BINARY EXPONENTIATIONx = 2.0 · n = 10

RESULT / BASE

result → 1

base → 2

STEP 1

10 in binary is 1010 — read its bits from the lowest. result starts at 1, base starts at 2.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/powx-n.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def myPow(self, x: float, n: int) -> float:
        exponent = n
        if exponent < 0:
            x = 1 / x
            exponent = -exponent

        result = 1.0
        base = x
        while exponent > 0:
            if exponent & 1:
                result *= base
            base *= base
            exponent >>= 1
        return result

TIME O(LOG N)SPACE O(1)PYTHON · RACE PACE · 15 LN

class Solution:
    def myPow(self, x: float, n: int) -> float:
        exponent = n
        if exponent < 0:
            x = 1 / x
            exponent = -exponent

        result = 1.0
        for _ in range(exponent):
            result *= x
        return result

TIME O(N)SPACE O(1)PYTHON · TRAINING PACE · 11 LN

class Solution {
    public double myPow(double x, int n) {
        long exponent = n;   // long avoids overflow when negating Integer.MIN_VALUE
        if (exponent < 0) {
            x = 1 / x;
            exponent = -exponent;
        }

        double result = 1.0;
        double base = x;
        while (exponent > 0) {
            if ((exponent & 1) == 1) {
                result *= base;
            }
            base *= base;
            exponent >>= 1;
        }
        return result;
    }
}

TIME O(LOG N)SPACE O(1)JAVA · RACE PACE · 20 LN

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

        double result = 1.0;
        for (long i = 0; i < exponent; i++) {
            result *= x;
        }
        return result;
    }
}

TIME O(N)SPACE O(1)JAVA · TRAINING PACE · 15 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED