50. Pow(x, n)

At a Glance

• Topic: math-geometry
• Pattern: Fast exponentiation (Divide & Conquer)
• Difficulty: Medium
• Companies: Amazon, Google, Meta, LinkedIn, Bloomberg
• Frequency: High
• LeetCode: 50

Problem (one-liner)

Implement base**exponent for floating base and signed 32-bit integer exponent, matching the problem's precision expectations. Avoid naive exponent multiplications.

Recognition Cues

• "Implement pow"
• Large magnitude exponent — requires logarithmic-time powering
• Negative exponent → reciprocal

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — multiply |exponent| times — O(|exponent|) — too slow.
• Better — exponentiation by squaring recursively — O(log |exponent|).
• Optimal — iterative binary exponentiation — O(log |exponent|) time / O(1) space — same complexity, constant stack.

Optimal Solution

Go

package main

func myPow(base float64, exponent int) float64 {
	if exponent < 0 {
		base = 1 / base
		exponent = -exponent
	}
	result := 1.0
	current := base
	for exponent > 0 {
		if exponent%2 == 1 {
			result *= current
		}
		current *= current
		exponent /= 2
	}
	return result
}

JavaScript

function myPow(base, exponent) {
	if (exponent < 0) {
		base = 1 / base;
		exponent = -exponent;
	}
	let result = 1;
	let current = base;
	while (exponent > 0) {
		if (exponent % 2 === 1) {
			result *= current;
		}
		current *= current;
		exponent = Math.floor(exponent / 2);
	}
	return result;
}

Walkthrough

Input: base = 2, exponent = 10 (binary 1010)

Invariant: result * current**exponent equals base**originalExponent (standard binary exp invariant).

Edge Cases

• exponent == 0 → 1 (including base == 0 per problem definition)
• Negative exponent
• base negative not required here (problem uses positive x typically)

Pitfalls

• Overflow in intermediates for integers — here float64 / JS number
• Forgetting to flip base when negating exponent before loop

Similar Problems

• 372. Super Pow — modular digit-array exponent.
• 043. Multiply Strings — composes multiplicative building blocks.

Variants

• Matrix exponentiation for Fibonacci / linear recurrences.
• Modular integer powmod for cryptography templates.

Mind-Map Tags

#fast-exponentiation #binary-exponentiation #divide-conquer #math