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.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

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

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

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