Skip to content

Volume ITechnology

4.28.6 — Pow(x, n) ​

LeetCode 50 · Medium

The problem ​

Compute x raised to the power n, where n may be negative.

Restating the Problem: You need to write a function that calculates x^n. The base x is a floating-point number, and the exponent n is an integer.

  • Constraints to note: n can be any 32-bit signed integer (from -2^{31} to 2^{31}-1). This means n can be huge, either positive or negative.
  • Edge cases: n = 0 should return 1. x = 0 is 0. If n is the minimum 32-bit integer, negating it directly causes an overflow in some languages.
pow(2.0, 10)    →  1024.0
pow(2.0, -2)    →  0.25
pow(2.1, 3)     →  9.261

n ranges over the full 32-bit signed integer range.

The brute force, and where it wastes work ​

The naive approach is simply running a loop n times, multiplying result by x in each iteration (and if n is negative, doing 1/x). While correct mathematically, this is an O(n) solution. If n = 2^{31}-1 (over 2 billion), this loop will take several seconds and result in a Time Limit Exceeded (TLE) error. We need something much faster.

The pattern ​

Multiplying x by itself n times is O(n) — two billion multiplications at the limit.

Fast exponentiation does it in O(\log n), using one identity:

x^n = \begin{cases} (x^{n/2})^2 & n \text{ even} \\ x \cdot x^{n-1} & n \text{ odd} \end{cases}

Each even step halves the exponent, so the number of steps is \log_2 n. For n = 1,000,000,000 that is about 30 multiplications instead of a billion.

The iterative form is easier to get right than the recursion, and it comes from reading the exponent in binary:

x^{13} = x^{8+4+1} = x^8 \cdot x^4 \cdot x^1

13 is 1101 in binary. So: square x repeatedly to get x^1, x^2, x^4, x^8, and multiply in the ones whose bit is set.

This is the same idea as binary representation itself, which is why it belongs next to the bit-manipulation chapter.

The negative-exponent trap ​

x^{-n} = 1 / x^n, so the obvious move is to negate n and invert at the end.

But negating the most negative 32-bit integer overflows. The range is -2^{31} to 2^{31}-1, so -(-2^{31}) does not fit.

In Python integers are unbounded and this cannot happen. In Java, C++ or C it can, and the standard fix is to widen n to a 64-bit type before negating.

Mention it. It is exactly the kind of detail that separates someone who has thought about the range from someone who has not, and this problem's constraints are worded to invite the question.

The solution ​

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

        result = 1.0  # (3)
        while n:  # (4)
            if n & 1:                 # (5) this bit of the exponent is set
                result *= x
            x *= x                    # (6) x, x², x⁴, x⁸, …
            n >>= 1                   # (7) move to the next bit

        return result  # (8)
ts
function myPow(x: number, n: number): number {
  if (n < 0) {  // (1)
    x = 1 / x;  // (2)
    n = -n;
  }

  let result = 1;  // (3)
  while (n > 0) {  // (4)
    if (n % 2 === 1) result *= x;  // (5)
    x *= x;  // (6)
    n = Math.floor(n / 2);  // (7)
  }

  return result;  // (8)
}

Line by line ​

This is fast exponentiation, also called exponentiation by squaring. It uses the fact that any whole-number power can be built from the powers x^1, x^2, x^4, x^8, \dots, one for each 1 in the exponent written in binary. For example, 13 is 1101 in binary, which is 8 + 4 + 1, so x^{13} = x^8 \times x^4 \times x^1.

(1) A negative power means "one over". x^{-n} = \frac{1}{x^n}.

(2) So flip x to 1 / x, and make n positive.

(3) The answer starts at 1, because multiplying by 1 changes nothing.

(4) Keep going while some bits of n are left.

(5) Is the lowest bit of n a 1? n & 1 keeps only the last binary digit. If it is 1, this power of x is part of the answer, so multiply it in. TypeScript checks the same thing with n % 2 === 1.

(6) Square x, so it moves on to the next power in the list: x, then x^2, then x^4, then x^8.

(7) Drop the lowest bit of n. n >>= 1 shifts every bit one place to the right, which is the same as halving and rounding down.

(8) The product of the powers whose bits were 1.

n & 1 tests the lowest bit — whether n is odd. n >>= 1 divides by two, discarding that bit. Together they walk the exponent's binary representation from the least significant end.

x *= x on every iteration, whether or not the bit was set, because the next bit represents twice the exponent.

Code Walkthrough:

  • Handling Negative Exponents: If n is negative, we invert x (x = 1/x) and make n positive. This turns x^{-n} into (1/x)^n.
  • Initialization: We set result = 1.0.
  • Iteration (while n): We loop as long as n > 0.
  • Applying Bits (if n & 1): We check if the lowest bit of n is 1 (i.e., n is odd). If it is, we multiply our result by the current weight of x.
  • Squaring the Base (x *= x): Regardless of the bit, we square x. This prepares x for the next bit position (e.g., passing from x^1 to x^2 to x^4).
  • Shifting the Exponent (n >>= 1): We shift n right by 1 bit, moving to the next most significant bit in the exponent.

result starts at 1, which is what makes n = 0 return 1 with no special case.

In JavaScript use Math.floor(n / 2) rather than n >>= 1 — the bitwise operators coerce to 32-bit signed integers, which would break for large n.

Trace ​

x = 2, n = 13 (binary 1101).

nbinarybit set?resultx
131101yes24
6110no216
311yes32256
11yes8192—

2^{13} = 8192 ✓. The multiplications used were x^1 \cdot x^4 \cdot x^8, matching 1101.

The recursive form ​

python
def myPow(self, x, n):
    if n < 0:
        return 1 / self.myPow(x, -n)
    if n == 0:
        return 1.0
    half = self.myPow(x, n // 2)
    return half * half if n % 2 == 0 else half * half * x

half must be computed once and reused. Writing myPow(x, n//2) * myPow(x, n//2) makes two recursive calls instead of one, and the whole thing collapses back to O(n). That is the classic mistake here, and it is the same "compute once, use twice" discipline as memoisation.

O(\log n) stack depth, which is fine at 32 levels.

Floating point honesty ​

Repeated multiplication accumulates rounding error. pow(2.0, 10) is exact because powers of two are exact in binary, but pow(2.1, 3) will be very slightly off from 9.261 — LeetCode accepts a small tolerance for this reason.

For integer bases with a modulus, the identical algorithm with % m after each multiplication is modular exponentiation, and it is the operation RSA is built on. Chapter 8 covers that, and mentioning it here shows the algorithm is not a puzzle.

Edge cases ​

  • n = 0. The loop never runs, and the answer is 1.
  • Negative n. Lines (1) and (2) turn it into a positive power of 1 / x.
  • x = 0 with negative n. That would be division by zero. The problem promises it never happens.
  • The most negative 32-bit n, -2^{31}. In Java or C++, making it positive overflows. Python and JavaScript numbers do not have that problem.

Complexity ​

O(\log n) time, O(1) space iteratively.

  • Time Complexity: O(\log n). In each step, we divide the exponent n by 2 (right shift). The number of times we can halve n before it reaches 0 is exactly bounded by the number of bits in n, which is \log_2(n) (at most 32 operations).
  • Space Complexity: O(1). The iterative version uses only a few variables (result, x, n) and requires no call stack. (The recursive version takes O(\log n) space due to the recursion stack).

Where this goes next ​

  • Modular exponentiation — the same loop with % m, and the core of RSA and Diffie-Hellman.
  • Matrix exponentiation — replace the multiplication with matrix multiplication and you can compute the n-th Fibonacci number in O(\log n). A neat connection back to 4.23.1.
  • Super Pow (LeetCode 372) — the exponent itself is an array of digits.
  • Sqrt(x) — binary search on the answer instead. 4.11.

What the interviewer will push on ​

"Why is it O(\log n)?" The exponent halves every iteration.

"What goes wrong with negative n?" Negating the most negative integer overflows in fixed-width languages.

"Why does the recursive version need half in a variable?" Two recursive calls would make it O(n).

"What about floating-point error?" It accumulates; exact answers need integer or rational arithmetic.

"What if you needed the result modulo something?" Apply % m after each multiplication — that is modular exponentiation, and it is what public-key cryptography runs on.

One thing to volunteer: explain the algorithm in terms of the exponent's binary digits. "13 is 1101, so I need x^8 \cdot x^4 \cdot x^1." It makes the loop obviously correct instead of a trick.

Next: 4.28.7 Multiply Strings — long multiplication, and the index formula that makes it work.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet