Faangprep Logo
Log inStart free
Browse curriculum

Pow(x, n)

Compute x to the power n in O(log n) by squaring: read n in binary and multiply in x^1, x^2, x^4, ... for every 1 bit.

MediumSolve on LeetCode

Problem Understanding

Pow(x, n): implement x raised to the power n, where x is a double and n is a 32-bit integer that may be negative.

Examples: x = 2, n = 10 returns 1024.00000; x = 2.1, n = 3 returns 9.26100; x = 2, n = -2 returns 0.25000.

The Intuition: Powers of Two Add Up to n

Multiplying x by itself n times is O(n), far too slow for n near 2³¹. But every n is a sum of powers of two, and exponents add:

  1. 10 = 8 + 2 (binary 1010), so x¹⁰ = x⁸ · x².
  2. The powers x, x², x⁴, x⁸, ... come from squaring: each is the previous one times itself.
  3. Read n one bit at a time from the lowest: square the base every round and multiply it into the result when the bit is 1.

That is about log₂ n squarings, at most 31 here. A negative n is handled up front with x⁻ⁿ = (1/x)ⁿ. The same halving idea drives binary search: each round cuts the remaining work in half.

Interactive Walkthrough

The bits of |n| are laid out with the power of x each one stands for. The bit being read is solid and bits already multiplied in turn green; the base and result are beside the figure. Try Example 3 to see a negative exponent flip to 1/x.

Dry Run Table

Input: x = 2, n = 10 (binary 1010)

Bit Value base Action result
0 0 2 (x¹) skip 1
1 1 4 (x²) result *= 4 4
2 0 16 (x⁴) skip 4
3 1 256 (x⁸) result *= 256 1024

Answer: x¹⁰ = x² · x⁸ = 1024.00000 in 4 rounds instead of 10 multiplications.

The Solution Template

Iterative squaring. Java, C++ and C copy n into a 64-bit integer so that -n is safe when n = -2³¹; JavaScript divides by 2 instead of shifting, because its bitwise operators work on 32-bit signed integers.

Pow(x, n) Code
1var myPow = function(x, n) {
2    if (n < 0) {
3        x = 1 / x;
4        n = -n;
5    }
6    let result = 1;
7    while (n > 0) {
8        if (n % 2 === 1) result *= x;
9        x *= x;
10        n = Math.floor(n / 2);
11    }
12    return result;
13};

Edge Cases & Common Mistakes

  • n = -2³¹: -n overflows a 32-bit int; widen to 64 bits before negating.
  • n = 0: the loop never runs and the answer is 1, even for x = 0 by LeetCode's convention.
  • Negative x: handled naturally; odd powers stay negative.
  • Bit tricks in JavaScript: n >> 1 and n & 1 convert to 32-bit signed ints, which breaks at 2³¹; use % 2 and Math.floor(n / 2).
  • Naive loop: n multiplications time out for n near 2³¹.

Summary

Flip a negative exponent to 1/x. Then read n bit by bit: square the base each round and multiply it into the result when the bit is 1. O(log n) time and O(1) space.

More practice: DSA interview questions with answers · patterns cheat sheet

Previous

Sum of Two Integers

Next

Reverse Integer

The approach, step by step

  1. Flip a negative exponent

    If n < 0, set x = 1 / x and n = -n, using a 64-bit integer for n.

  2. Walk the bits of n

    While n > 0: if the lowest bit is 1, result *= x. Then x *= x and shift n right by one.

  3. Return the result

    When n reaches 0, result holds x to the original power.

Frequently asked questions

How does fast exponentiation work?

Write n in binary, for example 10 = 1010. Then x^10 = x^8 · x^2. Keep a base that is squared every round, so it walks through x, x^2, x^4, x^8, and multiply it into the result whenever the matching bit of n is 1. That takes about log2(n) rounds instead of n.

How do you handle a negative n?

x^-n = (1/x)^n, so replace x with 1/x and n with -n. Store n in a 64-bit integer first: in Java, C++ and C, negating -2^31 overflows a 32-bit int.

Is there a recursive version?

Yes: pow(x, n) = pow(x, n / 2) squared, times x when n is odd. It does the same log n multiplications but uses O(log n) stack space; the loop version uses O(1).

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description