Definition
- Naive recursion –
power(x, n) = x * power(x, n-1)with base casepower(x, 0) = 1. Makes n multiplications in O(n) time. - Fast exponentiation – compute the half-power once, square it, and multiply by x if the exponent is odd. Reduces to O(log n) multiplications.
- Negative exponents –
x^(-n) = 1.0 / x^n. Promote to long before negating to avoid Integer.MIN_VALUE overflow. - BigDecimal – for money calculations, use arbitrary-precision BigDecimal instead of double.
- Stack depth – naive recurses n deep; fast recurses log n deep; iterative uses zero extra stack.
Suppose the National Bank of India computes how Rajesh's fixed deposit grows when a fixed growth factor is applied every year for several years. Applying the factor for five years is the factor multiplied by itself five times. The recursive idea is simple: growth over five years equals the factor times the growth over four years, and growth over zero years is just one, meaning no growth applied yet.
Understanding the Concepts
What is the Power of a Number problem?
Given a base x and an integer exponent n, compute x raised to the power n. This is LeetCode 50 (Pow(x, n)). The naive recursive approach follows the mathematical definition directly, and the optimized approach uses exponentiation by squaring to reduce the work from O(n) to O(log n).
package com.bank.service;
// Compute 1.05^10 for a fixed deposit growing at 5% annually for 10 years
// Naive: 10 multiplications
// Fast: about 4 multiplications (log2(10) ≈ 3.3)
How does the naive recursion work?
The base case is power(x, 0) = 1 because any number to the power zero is one. The recursive case is power(x, n) = x * power(x, n-1). Each call peels off one multiplication until the exponent reaches zero.
package com.bank.service;
public class NaivePower {
public static double power(double x, int n) {
if (n == 0) return 1.0;
return x * power(x, n - 1);
}
public static void main(String[] args) {
double factor = 1.05; // 5% annual growth
int years = 5;
System.out.println(factor + "^" + years + " = " + power(factor, years));
}
}
1.05^5 = 1.2762815625000003
This makes n multiplications and n stack frames, so it is O(n) time and O(n) stack space.
How does fast exponentiation work?
The insight is that x^n can be computed by halving the exponent. If n is even, x^n = (x^(n/2))^2. If n is odd, x^n = x * (x^(n/2))^2 (with integer division). This reduces the number of multiplications to about log2(n).
package com.bank.service;
public class FastPower {
public static double power(double x, long n) {
if (n == 0) return 1.0;
if (n < 0) {
x = 1.0 / x;
n = -n;
}
double half = power(x, n / 2);
double result = half * half;
if (n % 2 != 0) {
result *= x;
}
return result;
}
public static void main(String[] args) {
System.out.println("2^10 = " + power(2.0, 10));
System.out.println("1.05^30 = " + power(1.05, 30));
}
}
2^10 = 1024.0
1.05^30 = 4.321942375150668
How do you handle negative exponents?
A negative exponent means the reciprocal: x^(-n) = 1 / x^n. A subtle pitfall exists with Integer.MIN_VALUE because its absolute value exceeds Integer.MAX_VALUE. Negating it causes overflow. The solution is to promote to long before negating.
package com.bank.service;
public class NegativeExponentDemo {
public static double myPow(double x, int n) {
long exp = n; // promote to long to handle MIN_VALUE
if (exp < 0) {
x = 1.0 / x;
exp = -exp;
}
return fastPow(x, exp);
}
private static double fastPow(double x, long n) {
if (n == 0) return 1.0;
double half = fastPow(x, n / 2);
return (n % 2 == 0) ? half * half : half * half * x;
}
public static void main(String[] args) {
System.out.println("2^-3 = " + myPow(2.0, -3)); // 0.125
System.out.println("2^MIN = " + myPow(2.0, Integer.MIN_VALUE));
}
}
2^-3 = 0.125
2^MIN = 0.0
Why use BigDecimal for banking?
Using double for money calculations introduces binary floating-point rounding errors. For compounding interest at the National Bank of India, always use BigDecimal with explicit scale and rounding mode.
package com.bank.service;
import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;
public class BankingPower {
public static BigDecimal power(BigDecimal base, int exponent) {
if (exponent == 0) return BigDecimal.ONE;
BigDecimal half = power(base, exponent / 2);
BigDecimal squared = half.multiply(half);
if (exponent % 2 != 0) {
squared = squared.multiply(base);
}
return squared.setScale(10, RoundingMode.HALF_EVEN);
}
public static void main(String[] args) {
BigDecimal rate = new BigDecimal("1.085"); // 8.5% annual
BigDecimal principal = new BigDecimal("100000.00");
int years = 10;
BigDecimal factor = power(rate, years);
BigDecimal futureValue = principal.multiply(factor)
.setScale(2, RoundingMode.HALF_EVEN);
System.out.println("FD future value after " + years + " years: " + futureValue);
}
}
FD future value after 10 years: 226098.47
What about the iterative version?
The iterative squaring loop avoids all stack concerns. It processes the exponent bit by bit, squaring the base each iteration and multiplying into the result when the current bit is set.
package com.bank.service;
public class IterativePower {
public static double power(double x, int n) {
long exp = n;
if (exp < 0) {
x = 1.0 / x;
exp = -exp;
}
double result = 1.0;
double current = x;
while (exp > 0) {
if (exp % 2 == 1) {
result *= current;
}
current *= current;
exp /= 2;
}
return result;
}
public static void main(String[] args) {
System.out.println("2^10 = " + power(2.0, 10));
System.out.println("1.05^30 = " + power(1.05, 30));
}
}
2^10 = 1024.0
1.05^30 = 4.321942375150668
What are the edge cases?
- Exponent 0: any non-zero base to the power 0 is 1.
- Exponent 1: return x itself.
- Base 0: 0 to any positive power is 0. 0^0 is conventionally 1.
- Integer.MIN_VALUE: negation overflows; promote to long first.
- Very large exponent: the naive O(n) version is too slow; use O(log n).
package com.bank.service;
public class PowerEdgeCases {
public static void main(String[] args) {
System.out.println("x^0: " + FastPower.power(5.0, 0)); // 1.0
System.out.println("x^1: " + FastPower.power(5.0, 1)); // 5.0
System.out.println("0^5: " + FastPower.power(0.0, 5)); // 0.0
System.out.println("1^1000000: " + FastPower.power(1.0, 1000000)); // 1.0
}
}
x^0: 1.0
x^1: 5.0
0^5: 0.0
1^1000000: 1.0
What are common mistakes?
- Using
doublefor money and getting rounding drift. - Forgetting to handle negative exponents.
- Negating
Integer.MIN_VALUEwithout promoting tolong. - Using naive O(n) recursion when the exponent is large (e.g., 10^9), causing timeout.
// WRONG: double for money
double amount = 100000.0;
double rate = 1.085;
// After 30 years: rounding drift accumulates
// CORRECT: BigDecimal for money
BigDecimal amount2 = new BigDecimal("100000.00");
BigDecimal rate2 = new BigDecimal("1.085");
What are common interview follow-up questions?
- What is the time complexity of the fast version? (O(log n) multiplications.)
- Why promote to long? (Integer.MIN_VALUE cannot be negated in int.)
- Can you write it iteratively? (Yes, process bits of the exponent.)
- How do you handle 0^0? (Conventionally 1.)
- Why not use Math.pow? (It returns double, which is imprecise for money.)
Visual Overview
Fast Exponentiation: power(2, 10)
power(2, 10)
half = power(2, 5)
half = power(2, 2)
half = power(2, 1)
half = power(2, 0) = 1
return 1*1 * 2 = 2 (odd)
return 2*2 = 4 (even)
return 4*4 * 2 = 32 (odd)
return 32*32 = 1024 (even)
Only 4 calls instead of 10!
┌────────────────────────────────┐
│ Naive: O(n) multiplications │
│ Fast: O(log n) multiplications│
│ n=10 → 10 vs 4 │
│ n=1000000 → 1M vs 20 │
└────────────────────────────────┘
Key Takeaway
Raising a number to an integer power recursively follows the definition directly: power of x to n is x times power of x to n - 1, with the base case that any number to the power zero is one. That naive version does n multiplications and recurses n deep, so it is O(n) time.
The improvement is exponentiation by squaring. You compute the half-power once, square it, and multiply by x one extra time when the exponent is odd. That turns n multiplications into about log n, which is a huge saving for large exponents and only recurses about log n deep.
For banking at the National Bank of India, Rajesh projects the future value of fixed deposits by raising the annual growth factor to the number of years. He always uses BigDecimal with explicit scale and rounding mode because double introduces binary rounding drift that corrupts compounding to the paise level. The iterative squaring loop is preferred in production to avoid any stack concern.
The senior point is handling Integer.MIN_VALUE by promoting to long before negating, and knowing that Math.pow returns double which is unsuitable for exact money math. Explaining both the clean recursion and the logarithmic optimization, plus the BigDecimal precision requirement, shows the interviewer you understand recursion, complexity, and real financial constraints.
Remember one sentence: square the half-power for O(log n) and use BigDecimal for money.
---