Fast Power One Shot: Binary Exponentiation, Modular Exponentiation, and Pow(x, n)

1. Binary Exponentiation

Suppose aⁿ needs to be calculated quickly. The direct way multiplies a exactly n times, but binary exponentiation reduces the work by using the binary form of n and repeated squaring.

The useful property is that every exponent can be broken into powers of 2. Also, when n is even, aⁿ can be written as (a^(n/2)) × (a^(n/2)). When n is odd, one extra a is needed. This makes the exponent shrink fast, like a number sliding down a staircase two steps at a time.

Key Points

• Any number raised to power 0 is 1.

• If the exponent is even, the base can be squared and the exponent can be halved.

• If the exponent is odd, the current base contributes once to the answer.

• Binary exponentiation is also called exponentiation by squaring.

Algorithm

• Initialize answer as 1 because multiplying by 1 does not change the result.

• Keep the base as a and the exponent as n.

• Check whether the current exponent is odd. If it is odd, multiply answer by the current base because this power contributes to the final result.

• Square the base because the next power level is being prepared.

• Divide the exponent by 2 because one binary digit has been processed.

• Continue until the exponent becomes 0, then return answer.

Dry Run

Complexity Analysis

Time Complexity: O(log n), because the exponent is divided by 2 in every step.

Space Complexity: O(1), because only a few variables are maintained in the iterative version.

2. Modular Exponentiation

Sometimes the value of aⁿ becomes too large to store. In such cases, the task asks for (aⁿ) % mod instead of the full value. Modular exponentiation calculates the answer while keeping numbers small using modulo after multiplication.

The important property is that modulo can be applied at every multiplication step without changing the final remainder. So, instead of building a huge number first and taking modulo at the end, the answer is kept under control throughout the process.

Key Points

• Modular exponentiation is commonly used when answers are large.

• The modulo value must not be 0.

• Taking modulo after each multiplication prevents overflow in many cases.

• This technique is widely used in competitive programming and number theory.

Algorithm

• Initialize answer as 1 because it is the neutral starting value for multiplication.

• Reduce the base using a % mod so the base starts within the modulo range.

• Check whether the exponent is odd. If it is odd, multiply answer by base and take modulo.

• Square the base and take modulo again, because the next power is being prepared.

• Divide the exponent by 2 to process the next binary digit.

• Return answer when the exponent becomes 0.

Dry Run

Complexity Analysis

Time Complexity: O(log n), because the exponent is halved in every step.

Space Complexity: O(1), because only answer, base, exponent, and modulo are stored.

3. Pow(x, n)

The Pow(x, n) problem asks for x raised to power n, where x can be a decimal number and n can also be negative. For example, 2.0^-2 means 1 / 2.0², which is 0.25.

The main idea is still binary exponentiation, but negative exponents add one extra rule. If n is negative, xⁿ becomes

1 / x^(-n). Once the exponent is made positive, the same fast power logic can be used.

Key Points

• x⁰ is always 1.

• If n is negative, calculate the reciprocal: xⁿ = 1 / x^(-n).

• If x is 0, negative powers are usually invalid because division by 0 would occur.

• In fixed-size integer languages, very small negative values like -2³¹ need careful handling before negating.

Algorithm

• Handle n = 0 by returning 1, because any non-zero number raised to 0 is 1.

• If n is negative, invert the base as 1 / x and make the exponent positive as sign is handled separately.

• Initialize answer as 1.

• Use binary exponentiation on the positive exponent.

• Multiply answer by base whenever the current exponent is odd.

• Square the base and halve the exponent until the exponent becomes 0.

• Return answer.

Dry Run

Complexity Analysis

Time Complexity: O(log |n|), because the absolute exponent is divided by 2 in every step.

Space Complexity: O(1), because the iterative method uses only a few variables.