Abstract / Summary

Compute the power of a number x raised to exponent n efficiently.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 39% (7+ million submissions).

Typical patterns to solve this problem:

• Math
• Recursion

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The presented implementation computes the power of a floating-point base x raised to an integer exponent n. It follows a classic exponentiation-by-squaring strategy, augmented with early-exit checks for trivial inputs and a careful conversion of the exponent to a signed 64-bit integer to safely handle the most negative 32-bit value. The algorithm iteratively reduces the exponent while accumulating the result, using bitwise operations to distinguish odd and even states of the remaining exponent.

Early-exit handling

The function begins by addressing two special inputs that can be resolved without any iteration. When the base is zero, the mathematical result is zero for any non-zero exponent, and the code returns the base directly. When the exponent is zero, the mathematical identity x⁰ = 1 holds for any non-zero base, and the function returns 1. These checks avoid unnecessary work and also protect against division by zero later in the algorithm.

if (x == 0)
    return x;
if (n == 0)
    return 1;

Normalizing the exponent

The exponent n is originally a 32-bit signed integer. Converting it to a 64-bit signed integer N prevents overflow when the input is INT_MIN, whose absolute value cannot be represented in a 32-bit signed type. After the conversion, a negative exponent is handled by inverting the base (x = 1 / x) and negating the exponent (N = -N). This transformation turns the problem into computing a positive power, simplifying the loop logic.

int64_t N = n;
if (N < 0)
{
    x = 1 / x;
    N = -N;
}

Initializing the accumulator

The algorithm uses a variable result to accumulate the product of selected powers of x. It is initialized with the current base value, and the exponent is decremented by one because the first multiplication is already accounted for by this initialization. This design choice reduces the number of loop iterations by one.

double result = x;
N--;

Main loop - exponentiation by squaring

The core of the method is a while loop that runs while the remaining exponent N is greater than zero. Inside the loop, a bitwise test (N & 1) determines whether the current exponent is odd. If it is odd, the accumulator result is multiplied by the current base x, and the exponent is decremented to make it even. If the exponent is even, the base is squared (x *= x) and the exponent is halved using a right shift (N >>= 1). This pattern implements exponentiation by squaring, which dramatically reduces the number of multiplications compared to a naïve linear approach.

while (N > 0)
{
    if (N & 1)
    {
        result *= x;
        N--;
    }
    else
    {
        x *= x;
        N >>= 1;
    }
}

Edge-case coverage

The code explicitly handles the case where the base is zero, ensuring that a zero result is returned without performing division. The early return for an exponent of zero guarantees that 0⁰ yields 1, matching the conventional definition used in most programming contexts. By promoting the exponent to a 64-bit type before negation, the implementation safely processes the most negative 32-bit integer (INT_MIN), which would otherwise cause overflow when negated. The combination of these checks ensures correct behavior across the full range of valid inputs.

Performance optimizations

The algorithm avoids repeated multiplication by leveraging the binary representation of the exponent. Each iteration either multiplies the accumulator by the current base (when the least-significant bit is set) or squares the base and discards the processed bit (when the bit is zero). This reduces the total number of multiplications to roughly the number of bits set in the exponent plus the number of bits required to represent the exponent, which is far fewer than the linear count of n multiplications in a naïve loop.

Bitwise operations (& and >>) are used instead of modulo or division, providing faster execution on typical CPUs. The early decrement of N after initializing result eliminates one loop iteration, shaving off a constant amount of work. The use of a local double variable for the accumulator avoids repeated dereferencing of class members, keeping the hot loop tight and cache-friendly.

Overall, the implementation combines mathematical insight with low-level optimizations to deliver an efficient power function that works correctly for all edge cases defined by the input domain.

Imagine you have a magic calculator that needs to multiply a number by itself over and over again. Think of the number as x and the number of times it needs to be multiplied as n.

First, the code checks if the number is zero. If you multiply zero by itself, the answer is always zero. Then it checks if n is zero, which is like saying you want to multiply the number zero times. In the world of math, that just gives you one.

Sometimes n is a negative number. When that happens, the computer flips the number upside down to make the math easier to handle.

After that, the code uses a smart shortcut to get to the answer quickly. Instead of multiplying the number one step at a time, it looks for ways to double the speed. If n is an odd number, it multiplies the result once and makes n smaller. If n is an even number, it multiplies the number by itself to make a bigger chunk and then cuts n in half. It keeps doing this until the work is finished. It is a very fast way to reach a very big number without doing too many boring steps.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: logarithmic
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java						TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java	C#	Rust	JS	Go		TS
	LeetcodeHelp	C++	Python		Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	AdelDaniel									Dart
	aylei						Rust
	begeekmyfriend			C
	BigEggStudy					C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai				Java
	chenyanzhe	C++
	DimitrisJim			C
	everthis							JS
	fengvyi	C++
	gaosq0604		Python
	gouthampradhan				Java
	halfrost								Go
	haoel				Java
	JoshCrozier							JS
	keineahnung2345	C++
	Krazune			C
	lennylxx			C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	muhammadfarhankt								Go
	qiyuangong		Python
	ruoru						Rust
	Shamik07									Dart
	shreymehul					C#
	sonugiri1043	C++
	suxrobGM					C#
	varunu28				Java
	vli02			C
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
AdelDaniel	Dart
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
DimitrisJim	C
everthis	JavaScript
fengvyi	C++
gaosq0604	Python
gouthampradhan	Java
halfrost	Go
haoel	Java
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
muhammadfarhankt	Go
qiyuangong	Python
ruoru	Rust
Shamik07	Dart
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality