One of the most common interview questions involving recursion, mathematics, and binary thinking is implementing the power function efficiently.
Problem
Implement:
pow(x, n)
which calculates:
xⁿ
without using built-in power functions.
Brute Force Approach
Multiply x exactly n times.
double ans = 1.0;
for(int i = 0; i < n; i++) {
ans *= x;
}
Complexity
- Time: O(n)
- Space: O(1)
This works for small values but becomes inefficient when n is very large.
Key Observation
Let's calculate:
2¹⁰
Instead of multiplying 2 ten times:
2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2
we can use:
2¹⁰ = (2²)⁵
and
2² = 4
2⁴ = 16
2⁸ = 256
We're reducing the exponent by half every time.
This is called Binary Exponentiation.
Intuition
For every exponent:
If exponent is even
xⁿ = (x²)ⁿᐟ²
Example:
2¹⁰
→ 4⁵
If exponent is odd
Take one x into the answer and reduce exponent by one.
2⁵
→ 2 × 2⁴
Optimal Solution
class Solution {
public double myPow(double x, int n) {
long power = n;
double ans = 1.0;
if (power < 0) {
x = 1 / x;
power = -power;
}
while (power > 0) {
if (power % 2 == 0) {
x *= x;
power /= 2;
} else {
ans *= x;
power--;
}
}
return ans;
}
}
Dry Run
Input:
x = 2
n = 10
Initial:
ans = 1
Step 1:
10 is even
x = 4
power = 5
Step 2:
5 is odd
ans = 4
power = 4
Step 3:
4 is even
x = 16
power = 2
Step 4:
2 is even
x = 256
power = 1
Step 5:
1 is odd
ans = 1024
power = 0
Answer:
1024
Important Edge Case
Consider:
n = Integer.MIN_VALUE;
-2147483648
Doing:
n = -n;
causes overflow because:
2147483648
cannot fit inside an integer.
Therefore always store the exponent in:
long power = n;
before negating it.
Complexity Analysis
Time Complexity
O(log n)
The exponent is halved at every step.
Space Complexity
O(1)
Interview Takeaway
Whenever you see:
aᵇ
think:
Can I process the exponent bit by bit?
Binary Exponentiation is a powerful pattern that appears in:
- Fast Power
- Matrix Exponentiation
- Modular Arithmetic
- Competitive Programming
- System Design Calculations
Remember:
Odd exponent -> Take one x into answer
Even exponent -> Square x and halve exponent
That's the entire algorithm.
I'm currently solving the Striver SDE Sheet Challenge and documenting my learnings, patterns, mistakes, and interview insights along the way.
LinkedIn: https://www.linkedin.com/in/jaspreetsodhi482/
X (Twitter): https://x.com/Jaspree54799902
GitHub: https://github.com/codewithjaspreet