Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Implement fast exponentiation — reducing O(n) multiplications to O(log n) with binary exponentiation.
Implement pow(x, n), which calculates x raised to the power n (i.e., xn).
Example 1:
Input: x = 2.00000, n = 10 Output: 1024.00000
Example 2:
Input: x = 2.10000, n = 3 Output: 9.26100
Example 3:
Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25
Constraints:
-100.0 < x < 100.0-231 <= n <= 231-1n is an integer.x is not zero or n > 0.-104 <= xn <= 104The obvious approach: start with 1 and multiply by x a total of n times.
10 multiplications for n=10. For n=1,000,000,000 that's a billion multiplications — way too slow.
Key idea: Instead of multiplying one-by-one, we can square to double the exponent each time. 2^10 = (2^5)^2, and 2^5 = 2 * (2^2)^2. This reduces 10 multiplications to just 4.
Also called "exponentiation by squaring" or "fast power." The idea: express the exponent in binary, then use the binary digits to decide when to square and when to multiply.
The exponent n in binary tells us exactly which powers of x to multiply together. For n=10:
So x^10 = x^(8+2) = x^8 * x^2. We only multiply for the 1-bits. The base x is squared each iteration to produce x^1, x^2, x^4, x^8, ...
The iterative approach processes bits from right to left. In each loop iteration: if the current bit is 1, multiply result by x. Then square x (to prepare the next power), and right-shift n. The loop runs log(n) times — one iteration per bit.
Let's trace through the algorithm step by step, showing how the binary representation of 10 drives the computation.
| Iter | N (binary) | N % 2 | Action | result | x |
|---|---|---|---|---|---|
| 1 | 1010 | 0 | square x only | 1 | 4 |
| 2 | 101 | 1 | result *= x, square x | 4 | 16 |
| 3 | 10 | 0 | square x only | 4 | 256 |
| 4 | 1 | 1 | result *= x, square x | 1024 | 65536 |
After 4 iterations (log2(10) = ~3.3, rounded up to 4), N becomes 0 and the loop ends. result = 1024 = 2^10.
Only the powers corresponding to 1-bits in 10 (binary 1010) are multiplied into the result: 2^8 and 2^2.
x = 1/x and N = -N. Then proceed with positive exponent.-Integer.MIN_VALUE overflows in 32-bit int. Solution: use a long variable for N. long N = n; then N = -N; works correctly.class Solution { public double myPow(double x, int n) { // Use long to handle Integer.MIN_VALUE edge case long N = n; // Negative exponent: x^(-n) = (1/x)^n if (N < 0) { x = 1 / x; N = -N; } double result = 1; // Process each bit of N from right to left while (N > 0) { if (N % 2 == 1) // Current bit is 1 result *= x; // Multiply this power into result x *= x; // Square x for next power: x^1→x^2→x^4→x^8... N /= 2; // Right-shift: move to next bit } return result; } }
func myPow(x float64, n int) float64 { // Negative exponent: x^(-n) = (1/x)^n N := n if N < 0 { x = 1 / x N = -N } result := 1.0 // Process each bit of N from right to left for N > 0 { if N%2 == 1 { // Current bit is 1 result *= x // Multiply this power into result } x *= x // Square x for next power: x^1→x^2→x^4→x^8... N /= 2 // Right-shift: move to next bit } return result }
def my_pow(x: float, n: int) -> float: # Negative exponent: x^(-n) = (1/x)^n N = abs(n) if n < 0: x = 1 / x result = 1.0 # Process each bit of N from right to left while N > 0: if N % 2 == 1: # Current bit is 1 result *= x # Multiply this power into result x *= x # Square x for next power: x^1→x^2→x^4→x^8... N //= 2 # Right-shift: move to next bit return result
impl Solution { pub fn my_pow(mut x: f64, n: i32) -> f64 { // Use i64 to handle i32::MIN edge case let mut N = n as i64; // Negative exponent: x^(-n) = (1/x)^n if N < 0 { x = 1.0 / x; N = -N; } let mut result = 1.0f64; // Process each bit of N from right to left while N > 0 { if N % 2 == 1 { // Current bit is 1 result *= x; // Multiply this power into result } x *= x; // Square x for next power: x^1→x^2→x^4→x^8... N /= 2; // Right-shift: move to next bit } result } }
function myPow(x: number, n: number): number { // Negative exponent: x^(-n) = (1/x)^n let N = Math.abs(n); if (n < 0) x = 1 / x; let result = 1; // Process each bit of N from right to left while (N > 0) { if (N % 2 === 1) // Current bit is 1 result *= x; // Multiply this power into result x *= x; // Square x for next power: x^1→x^2→x^4→x^8... N = Math.floor(N / 2); // Right-shift: move to next bit } return result; }
Enter x and n, then step through the binary exponentiation loop. Watch the binary representation of n drive the computation.
The loop runs once per bit of n, which is O(log n) iterations. Each iteration does O(1) work (one or two multiplications). The iterative approach uses only a few variables -- no recursion stack needed. The recursive version uses O(log n) stack space.
A single loop multiplies result by x exactly n times, performing one floating-point multiplication per iteration. For n = 231-1 this means over two billion multiplications -- far too slow. Only a running product variable is needed, so space is O(1).
Binary exponentiation processes one bit of n per iteration, halving n each time -- so the loop runs at most log2(n) times (~31 iterations for 32-bit n). Each iteration does at most two multiplications (square + conditional multiply). Only a few scalar variables are used.
Each recursive step halves n -- turning O(n) multiplications into O(log n). Handle negative n by computing 1/x|n|. This same binary exponentiation technique powers modular exponentiation (RSA), matrix exponentiation (Fibonacci in O(log n)), and many competitive programming algorithms.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.