Binary Exponentiation
Binary Exponentiation
Pattern: Divide and Conquer (specifically, Decrease and Conquer)
Idea: Halve the exponent at each step, square the result, and multiply by the base only if the exponent was odd.
💻 Code
Iterative (preferred) :-
def power(x, n):
result = 1
while n > 0:
if n & 1:
result *= x
x *= x
n //= 2
return resultTime complexity - O(logn) Aux. Space complexity - O(1)
Recursive :-
def power(x, n):
if n == 0:
return 1
temp = power(x, n // 2)
if n % 2 == 0:
return temp * temp
return x * temp * tempTime complexity - O(log n) Aux. Space complexity - O(log n) . Function call stack
NOTE: With Modulo
Computing Power (Binary Exponentiation / Exponentiation by Squaring)
The Computing Power problem asks us to compute
xⁿefficiently.
It is one of the most fundamental algorithms in mathematics, competitive programming, and cryptography.
The naive solution requires n multiplications.
Using Binary Exponentiation, we can reduce this to only O(log n) multiplications.
Problem Statement
Given two integers
xand
ncompute
xⁿExample
2⁵ = 32
3⁴ = 81
5⁰ = 1Naive Approach
Idea
Multiply the number by itself exactly n times.
Example
2⁵
= 2 × 2 × 2 × 2 × 2Algorithm
def power(x, n):
result = 1
for _ in range(n):
result *= x
return resultTime Complexity
The loop executes exactly n times.
Therefore,
Time Complexity = O(n)Auxiliary Space Complexity
Only one extra variable is used.
Auxiliary Space Complexity = O(1)Key Mathematical Observation
Suppose we want
x⁸Instead of multiplying
x × x × x × x × x × x × x × xnotice
x⁸
= (x⁴)²
= ((x²)²)²We repeatedly square the answer.
Now consider
x⁹x⁹
= x × x⁸Similarly,
x¹³
= x × (x⁶)²
= x × (x³)²
= x × x × (x²)²The exponent keeps getting divided by 2.
This immediately suggests an algorithm whose work is proportional to
log₂(n)instead of
nEven and Odd Exponents
Every exponent belongs to one of two cases.
Case 1 — Even Exponent
Suppose
n = 8Then
x⁸
= (x⁴)²Generally,
If n is even,
xⁿ = (xⁿ⁄²)²Case 2 — Odd Exponent
Suppose
n = 9Then
x⁹
= x × x⁸
= x × (x⁴)²Generally,
If n is odd,
xⁿ = x × (x⁽ⁿ⁻¹⁾⁄²)²These two identities are the entire foundation of Binary Exponentiation.
Recursive Binary Exponentiation
Algorithm
def power(x, n):
if n == 0:
return 1
temp = power(x, n // 2)
if n % 2 == 0:
return temp * temp
return x * temp * tempDry Run
Compute
2¹³Recursive calls
power(2,13)
↓
power(2,6)
↓
power(2,3)
↓
power(2,1)
↓
power(2,0)Now unwind
2⁰ = 1
↓
2¹ = 2
↓
2³ = 8
↓
2⁶ = 64
↓
2¹³ = 8192Notice that every recursive call halves the exponent.
Time Complexity
At every recursive call,
the exponent becomes
n
↓
n/2
↓
n/4
↓
n/8
...How many times can we divide by 2?
Exactly
log₂(n)times.
Each recursive call performs only constant work.
Therefore,
Time Complexity = O(log n)Auxiliary Space Complexity
The recursion depth is
O(log n)Hence,
Auxiliary Space Complexity = O(log n)Iterative Binary Exponentiation
The recursive solution can be converted into an iterative one.
The trick is to look at the binary representation of the exponent.
Example
13
= 1101₂Observe
13
= 8 + 4 + 1Therefore,
x¹³
= x⁸ × x⁴ × x¹While traversing the bits,
we continuously square the base.
Whenever a bit is
1we include the current power in the answer.
Algorithm
def power(x, n):
result = 1
while n > 0:
if n & 1:
result *= x
x *= x
n //= 2
return resultDry Run
Compute
3¹³Binary representation
13
1101₂| n | Binary | Current x | Result |
|---|---|---|---|
| 13 | 1101 | 3 | 1 |
| 6 | 110 | 9 | 3 |
| 3 | 11 | 81 | 3 |
| 1 | 1 | 6561 | 243 |
| 0 | 0 | 43046721 | 1594323 |
Final Answer
1594323which is
3¹³Why Does This Work?
Every iteration
n //= 2removes the least significant binary digit.
Every iteration
x *= xmoves to the next power of two.
Example
3
↓
3²
↓
3⁴
↓
3⁸
↓
3¹⁶Whenever the current binary digit is
1that power contributes to the final answer.
Example
Compute
2¹³Binary
1101₂Selected powers
2¹
2⁴
2⁸Multiply them
2 × 16 × 256
= 8192Exactly
2¹³Complexity Analysis
The exponent becomes
n
↓
n/2
↓
n/4
↓
...The loop executes
O(log n)times.
Each iteration performs constant work.
Therefore,
Time Complexity = O(log n)Auxiliary Space Complexity
No recursion.
Only a few variables.
Auxiliary Space Complexity = O(1)Common Misconceptions
❌ Why is it called Binary Exponentiation?
Because the exponent is processed according to its binary representation, not because the base is binary.
❌ Why do we square the base every iteration?
Each squaring generates the next power of two.
x
↓
x²
↓
x⁴
↓
x⁸
↓
x¹⁶❌ Why divide the exponent by 2?
Each division removes one binary digit.
The number of binary digits in n is
⌊log₂(n)⌋ + 1Hence only O(log n) iterations are needed.
Key Realizations 💡
-
Binary Exponentiation is based on repeatedly halving the exponent.
-
Every exponent can be decomposed into powers of two using its binary representation.
-
Even exponents are solved by squaring.
-
Odd exponents require one extra multiplication by the base.
-
The recursive and iterative algorithms have the same time complexity.
-
The iterative version is usually preferred because it uses constant auxiliary space.
Complexity Summary
| Approach | Time | Auxiliary Space |
|---|---|---|
| Naive Multiplication | O(n) | O(1) |
| Recursive Binary Exponentiation | O(log n) | O(log n) |
| Iterative Binary Exponentiation | O(log n) | O(1) |
Interview Takeaways 🎯
-
Always recognize exponentiation as a problem where the exponent can be halved repeatedly.
-
Derive the recurrence from the two identities:
-
Even:
xⁿ = (xⁿ⁄²)² -
Odd:
xⁿ = x × (x⁽ⁿ⁻¹⁾⁄²)²
-
-
In interviews and competitive programming, the iterative binary exponentiation solution is generally preferred because it achieves O(log n) time with O(1) auxiliary space.
-
Binary Exponentiation is also the foundation for Modular Exponentiation, one of the most frequently used algorithms in number theory and competitive programming.