Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Pow(x, n) in Java: Halve the Exponent Safely

Learn exponentiation by squaring, negative exponents, Integer.MIN_VALUE safety and the real call chain through commented Java.

MediumRecursion and backtrackingPattern: recursion

Problem statement

Implement myPow(x,n) to return a double representing x raised to the integer exponent n. Positive powers multiply factors of x; a negative power uses the reciprocal: 2^-2 = 1/4.

The LeetCode contract uses a signed 32-bit exponent and excludes zero when n is nonpositive. The supplied source includes a six-decimal display instruction, but formatting is separate from returning a double. The teaching driver prints the numerical result directly.

Constraints & requirements

CONTRACT
Use a 32-bit int exponent. Valid input excludes zero with a nonpositive exponent. Convert n to long before negating Integer.MIN_VALUE. Decimal formatting is a driver concern.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    x=2.0; n=10
    Output
    1024.0

    Halving needs only a short chain of calls instead of ten repeated factors.

  2. Example 2 Case 2

    Input
    x=2.0; n=-2
    Output
    0.25

    Use the reciprocal base and positive exponent.

  3. Example 3 Case 3

    Input
    x=-1.0; n=-2147483648
    Output
    1.0

    The smallest int exponent has an even positive magnitude that fits long.

Solve on LeetCode ↗

Hints Optional

Hints become more specific one step at a time.
01Hint 1

Express x^n using x^(n/2).

02Hint 2

Compute the smaller power once; square it and add x only for odd n.

03Hint 3

Widen the exponent before negation; Java evaluates -n as int if n is int.

How to think before coding

Define positivePower(x,k) for a nonnegative exponent. k==0 returns the multiplicative identity 1. One child calculates x^(k/2); squaring supplies the even part, and k%2 decides whether one extra x is needed. Store that child result: calling the helper twice discards the reuse that makes the method logarithmic. Normalize a negative exponent in the public wrapper.

Brute force and the improvement

Multiply x by itself |n| times; for a negative exponent, use the reciprocal base and positive magnitude. This costs O(|n|) time and O(1) extra space, and is a useful small-input oracle. It is far too much repeated work for a large exponent. Compute the half power ONCE, square it, and multiply by x only for an odd exponent. Halving reaches O(log |n|) calls. Widen the int exponent to long BEFORE negating it, including Integer.MIN_VALUE.

Intuition: reuse a smaller answer

For 2^10, calculate 2^5 once and square it. For 2^5, calculate 2^2, square it, then multiply by one extra 2.

For nonnegative n, integer division gives n = 2·floor(n/2) + (n mod 2). That explains both cases. Even exponents need only the square; odd exponents need one extra factor. Each child solves an exponent about half as large, so the call chain shrinks quickly.

This is not a binary recursion tree. Calling pow(x,n/2) twice throws away reuse and changes the time bound. Store the returned value in half and multiply it by itself.

Algorithm

  1. Copy the int exponent into a long.
  2. If it is negative, replace x with 1/x and negate the long exponent.
  3. Return 1 when the remaining exponent is zero.
  4. Recursively find the half power once.
  5. Square it; multiply by x only for an odd exponent.

Java solution

Convert the exponent to long before negating it. Passing an already-overflowed -n into a long parameter would be too late for Integer.MIN_VALUE.

Java
import java.util.*;

class Solution {
    public static double myPow(double x, int n) {
        long exponent = n; // Widen BEFORE negation: -Integer.MIN_VALUE does not fit in int.
        if (exponent < 0) {
            x = 1.0 / x; // x^(-k) equals (1/x)^k; valid input excludes zero with negative power.
            exponent = -exponent; // Safe now, including the exponent -2,147,483,648.
        }
        return positivePower(x, exponent); // This helper sees only nonnegative exponents.
    }
    private static double positivePower(double x, long n) {
        if (n == 0) return 1.0; // Multiplication identity: no factors remain.
        double half = positivePower(x, n / 2); // Compute the smaller power ONCE, not twice.
        double square = half * half; // Supply 2 * floor(n/2) factors of x.
        return n % 2 == 0 ? square : square * x; // An odd exponent needs one extra factor.
    }

    public static void main(String[] args) {
        System.out.println(myPow(2.0, -2)); // 0.25
    }
}

The default invocation returns 0.25. myPow(-1.0, Integer.MIN_VALUE) returns 1 without overflowing the exponent. Java floating-point arithmetic is approximate; compare ordinary decimal examples with a tolerance, not exact decimal equality.

Call chain and dry run

Numbered illustrated dry run for Pow(x, n); the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

Follow the Java, step by step

Example: x = 2.0, n = -2

What to track: Track the normalized base and each helper frame’s exponent. The multiplication happens while calls return, not while descending.

  1. Normalize the negative exponent

    Java operationx = 1.0 / x;
    Statex = 0.5; exponent is widened to long, then negated to 2

    The reciprocal turns the problem into a nonnegative power. Widening first also handles Integer.MIN_VALUE safely.

  2. Descend once per frame

    Java operationdouble half = positivePower(x, n / 2);
    Stateactive calls: positivePower(0.5,2) → positivePower(0.5,1) → positivePower(0.5,0)

    The two non-base frames wait for their single child; half is not available yet.

  3. Return the multiplication identity

    Java operationif (n == 0) return 1.0;
    Statethe n = 0 call returns 1.0 to the n = 1 frame

    A power of zero contains no factors, so the identity is 1, not 0.

  4. Resume the odd exponent

    Java operationreturn n % 2 == 0 ? square : square * x;
    Staten = 1; half = 1; square = 1; return 1 × 0.5 = 0.5

    An odd exponent needs one extra base after squaring the half-power.

  5. Resume the even exponent

    Java operationdouble square = half * half;
    Staten = 2; half = 0.5; square = 0.25; return 0.25

    Two equal half-powers already supply both factors. No extra multiplication by x is needed.

Final result: 0.25

Worked example · read from top to bottom
positivePower(2,10)
  → positivePower(2,5)
    → positivePower(2,2)
      → positivePower(2,1)
        → positivePower(2,0) returns 1
      n=1: 1×1×2 = 2
    n=2: 2×2 = 4
  n=5: 4×4×2 = 32
n=10: 32×32 = 1024

The waiting calls retain their own n. Returning from n=0 does not make every caller’s n zero. Each caller combines the child’s answer according to its own even/odd case.

Why it works

The base case returns the multiplication identity. Assuming the child correctly returns x^floor(n/2), squaring gives the power with twice that exponent. The odd case contributes the missing final factor. Converting (x,-k) into (1/x,k) preserves the mathematical answer.

Complexity and alternative approaches

For exponent magnitude E, time and recursive auxiliary space are O(log(E+1)). Zero takes constant time. Only one recursive child is evaluated per level.

Repeated multiplication costs O(E), which is unusable for very large exponents. Iterative binary exponentiation performs the same squaring decisions with O(1) extra space and avoids recursive calls. Math.pow is useful in application code but does not demonstrate the requested algorithm.

Reciprocal-first evaluation avoids creating a huge positive power merely to invert it, though double overflow/underflow and rounding still follow floating-point limits.

Common mistakes

  • long exponent = -n still negates n as an int. Widen first.
  • Taking the absolute value of Integer.MIN_VALUE in int is also unsafe.
  • Forgetting the extra x for odd n produces the wrong power.
  • Returning zero for exponent zero breaks the multiplicative identity.
  • Forcing six-decimal output inside a method that must return double changes its return contract.

Practice next

Next lessonrecursive insertion sort

Back to Recursion and backtracking →