Pow(x, n)

Problem in Plain English

Compute x raised to the integer power n, handling negative exponents through reciprocals and full 32-bit exponents with only logarithmically many multiplications.

Problem Statement

Implement pow(x, n): raise the base x to the integer power n and return the result as a floating-point number.

The exponent may be negative, meaning the reciprocal (so $x^{-2} = 1 / x^2$ ), and n can stretch across the whole 32-bit range, where multiplying x by itself n times is far too slow. Note that negating the smallest 32-bit value overflows it, so widen n before flipping its sign.

Constraints

$-100 < x < 100$ .
$-2^{31} \leq n \leq 2^{31}-1$ .
n is an integer.
Either x is nonzero or n is positive.
$-10^4 \leq x^n \leq 10^4$ .

Examples

Example 1

Input: x = 2.00000, n = 10
Output: 1024.00000

Multiplying 2 by itself ten times yields 1024.

Example 2

Input: x = 2.10000, n = 3
Output: 9.26100

Three factors of 2.1 give $2.1 \times 2.1 \times 2.1 = 9.261$ . Floating-point arithmetic may return a nearby representation.

Example 3

Input: x = 2.00000, n = -2
Output: 0.25000

A negative exponent uses the reciprocal: $2^{-2} = (1/2)^2 = 0.25$ .

Example 4

Input: x = -3.00000, n = 0
Output: 1.00000

Zero factors form the empty product, one. Neither loop performs any multiplication.

Example 5

Input: x = -1.00000, n = -2147483648
Output: 1.00000

After reciprocating the base, the positive magnitude 2147483648 is even. An even number of factors of -1 gives 1; Java must widen before negating the exponent.

Intuition

Exponentiation counts equal factors. Example 1 asks for ten factors of 2, but we can form powers 2, 4, 16 and 256 by repeatedly squaring. Since ten equals eight plus two, multiplying 256 by 4 produces 1024. A negative exponent changes the base to its reciprocal first; exponent zero uses the empty product, one.

Approaches

Repeated Multiply

Solution Details

Reveal Repeated Multiply: intuition, complexity, and code

Intuition

The definition of a power is repeated multiplication: $x^{10}$ is x multiplied by itself ten times. Flipping a negative exponent into a reciprocal up front leaves a simple loop that multiplies an answer accumulator exactly n times.

Step-by-Step Logic

Check unit bases first: return 1 for base 1, and use exponent parity for base -1. Otherwise copy the exponent to a type that can hold its positive magnitude. For negative exponents, reciprocate the base and negate the widened exponent. Example 1 keeps base 2 and magnitude 10.
Start ans at 1 and iterate once per unit of the nonnegative magnitude. After k iterations, ans represents k factors of the normalized base.
Multiply ans by the base on every pass; Example 1 progresses through 2, 4, 8 and the remaining powers through 1024.
Return ans after all factors are consumed. A zero exponent returns the initial one; Example 1 returns 1024. This baseline is impractical for full-range exponents except the explicitly handled unit bases.

Why It Works

The shortcuts are exact: 1 raised to any integer power is 1; powers of -1 are 1 for even exponents and -1 for odd exponents, including negative exponents because the reciprocal of -1 is -1. For other bases, let b be the original base for a nonnegative exponent, or its reciprocal for a negative exponent, and let e be the nonnegative exponent magnitude. After k loop iterations, ans equals b raised to k in exact arithmetic: it starts at one, and multiplying by b adds one factor. After exactly e iterations, ans is the requested power. When e is zero the loop is empty and returns one. Floating-point operations round each multiplication, so the computed result approximates this mathematical invariant.

Dry Run

Repeated Multiply: variable states at each step
Pass	Remaining before	ans before	ans after multiplying by 2	Remaining after
initialize	10	1	1	10
1	10	1	2	9
2	9	2	4	8
3	8	4	8	7
4	7	8	16	6
5	6	16	32	5
6	5	32	64	4
7	4	64	128	3
8	3	128	256	2
9	2	256	512	1
10	1	512	1024	0
return	0	1024	1024	0

Complexity Analysis

Time Complexity

O(|n| + 1)

Space Complexity

O(1)

For a general base, the baseline performs exactly |n| multiplications; the +1 accounts for initialization and n = 0. Unit bases 1 and -1 have constant-time shortcuts, but worst-case time remains linear in the exponent magnitude, which can be 2147483648. A few fixed-size floating-point and exponent variables use constant auxiliary storage. Python integers need at most 32 magnitude bits under the stated bound.

Code

Solution.java

1class Solution {2    public double myPow(double x, int n) {3        // Unit bases need no repeated work, even at full exponent bounds.4        if (x == 1.0) return 1.0;5        if (x == -1.0) return n % 2 == 0 ? 1.0 : -1.0;6        // Widen first: negating INT_MIN in int would overflow.7        long exp = n;8        if (exp < 0) {9            x = 1.0 / x;10            exp = -exp;11        }12        double ans = 1.0;13        for (long i = 0; i < exp; i++) {14            ans *= x;15        }16        return ans;17    }18}

Hints

Hint 1

Group equal factors by squaring: ten factors of 2 can be assembled from powers with exponents eight and two.

Hint 2

If the remaining exponent is odd, consume one factor before halving; if it is even, square the base and halve directly.

Hint 3

Maintain ans times base raised to exp as the normalized target power. Reciprocate for negative n and widen the Java exponent before negation.

Edge Cases

A nonzero base with n = 0 returns 1; zero to zero and zero to a negative exponent are excluded by the contract.
A zero base with positive n returns zero. Negative bases produce a negative answer only for odd exponent magnitude.
INT_MIN = -2147483648 requires positive magnitude 2147483648, which does not fit Java int; JavaScript Number and Python int represent it exactly.
Bases 1 and -1 remain unit magnitude for every exponent; parity determines the sign for -1.
Very large positive or negative exponents can underflow toward zero. Compare floating-point outputs using a tolerance rather than exact equality.

Common Mistakes and Interview Tips

Negating the Java int before widening overflows at INT_MIN; assign to long first.
Using JavaScript signed bitwise shifts on magnitude 2147483648 can make it negative; use Math.floor(exp / 2).
Forgetting the reciprocal for a negative exponent computes the opposite power.
Changing base before consuming an odd factor includes the wrong squared power in ans.
Interview tip: state the invariant, explain the odd/even cases, and distinguish the exact-arithmetic proof from floating-point rounding.
The repeated multiplication baseline needs billions of operations on general full-range inputs; use binary exponentiation for the complete constraints.

Key Takeaway

Halving the exponent while squaring the base converts linear repeated work into logarithmic work, the same idea behind fast modular exponentiation.