Pow(x, n) - Fast Exponentiation

🎯

Pow(x, n) - Fast Exponentiation

mediumBINARY_SEARCHAmazonGoogleMicrosoft

Imagine you need to calculate compound interest or large powers efficiently in financial software or scientific simulations where performance matters.

💡 This problem is about efficiently computing powers, which beginners often try to solve by multiplying the base repeatedly. This naive approach is slow and impractical for large exponents. Understanding how to reduce the number of multiplications using divide and conquer is key.

📋

Problem Statement

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n). Given a floating-point number x and an integer n, return the value of x raised to the power n.

−100.0 < x < 100.0−2^31 <= n <= 2^31 − 1n is an integerResult will be within the range of a 64-bit floating point number

💡

Example

Input"x = 2.0, n = 10"

Output1024.0

2^10 = 1024, computed by repeated multiplication or fast exponentiation

Input"x = 2.1, n = 3"

Output9.261

2.1^3 = 2.1 * 2.1 * 2.1 = 9.261

Input"x = 2.0, n = -2"

Output0.25

2^-2 = 1 / (2^2) = 1/4 = 0.25

• n = 0 → output 1 (any number to power 0 is 1)
• n = 1 → output x (power 1 is the number itself)
• n = -1 → output 1/x (negative powers invert the base)
• x = 0 and n > 0 → output 0 (zero to positive power is zero)

⚠️

Common Mistakes

Not handling negative exponents correctly

Incorrect results or division by zero errors

✅ Check if n is negative, convert to positive, and invert the final result

Using int for n without handling overflow

Overflow leads to incorrect calculations or runtime errors

✅ Use long or long long to store absolute value of n safely

Not handling n=0 case explicitly

May cause infinite recursion or wrong output

✅ Return 1 immediately when n is zero

Using recursion without tail call optimization

Stack overflow for large n

✅ Use iterative binary exponentiation to avoid recursion depth issues

Multiplying result by x before squaring in odd n case incorrectly

Wrong final result

✅ Square half first, then multiply by x if n is odd

🧠

Brute Force (Iterative Multiplication)

💡 This approach exists to establish the baseline understanding of the problem by directly implementing the definition of power. It is simple but inefficient for large n.

Intuition

Multiply x by itself n times to get x^n. For negative n, compute the positive power and take reciprocal.

Algorithm

1. If n is zero, return 1 immediately.
2. If n is negative, convert n to positive and remember to invert the result later.
3. Initialize result as 1.
4. Multiply result by x, n times in a loop.
5. If original n was negative, return 1/result; else return result.

💡 This algorithm is easy to implement but inefficient because it does not reduce the number of multiplications.

</>

Code

def myPow(x: float, n: int) -> float:
    if n == 0:
        return 1.0
    negative = n < 0
    n = abs(n)
    result = 1.0
    for _ in range(n):
        result *= x
    return 1 / result if negative else result

# Driver code
if __name__ == '__main__':
    print(myPow(2.0, 10))  # Expected: 1024.0
    print(myPow(2.1, 3))   # Expected: 9.261
    print(myPow(2.0, -2))  # Expected: 0.25

Line Notes

if n == 0:Handle the base case where any number to power 0 is 1

negative = n < 0Check if exponent is negative to invert result later

for _ in range(n):Multiply x by itself n times, the core brute force loop

return 1 / result if negative else resultInvert the result if original exponent was negative

public class Solution {
    public static double myPow(double x, int n) {
        if (n == 0) return 1.0;
        boolean negative = n < 0;
        long N = Math.abs((long)n); // Use long to avoid overflow
        double result = 1.0;
        for (long i = 0; i < N; i++) {
            result *= x;
        }
        return negative ? 1 / result : result;
    }

    public static void main(String[] args) {
        System.out.println(myPow(2.0, 10)); // 1024.0
        System.out.println(myPow(2.1, 3));  // 9.261
        System.out.println(myPow(2.0, -2)); // 0.25
    }
}

Line Notes

if (n == 0) return 1.0;Immediate return for exponent zero

boolean negative = n < 0;Flag to track negative exponent

long N = Math.abs((long)n);Convert to long and absolute to handle edge cases safely

for (long i = 0; i < N; i++) {Loop to multiply x by itself N times

return negative ? 1 / result : result;Invert the result if original exponent was negative

#include <iostream>
#include <cmath>
using namespace std;

double myPow(double x, int n) {
    if (n == 0) return 1.0;
    bool negative = n < 0;
    long long N = abs((long long)n);
    double result = 1.0;
    for (long long i = 0; i < N; i++) {
        result *= x;
    }
    return negative ? 1 / result : result;
}

int main() {
    cout << myPow(2.0, 10) << endl; // 1024.0
    cout << myPow(2.1, 3) << endl;  // 9.261
    cout << myPow(2.0, -2) << endl; // 0.25
    return 0;
}

Line Notes

if (n == 0) return 1.0;Handle zero exponent base case

bool negative = n < 0;Track if exponent is negative

long long N = abs((long long)n);Use long long to avoid overflow and get absolute value

for (long long i = 0; i < N; i++) {Multiply x by itself N times in loop

return negative ? 1 / result : result;Invert the result if original exponent was negative

function myPow(x, n) {
    if (n === 0) return 1.0;
    let negative = n < 0;
    n = Math.abs(n);
    let result = 1.0;
    for (let i = 0; i < n; i++) {
        result *= x;
    }
    return negative ? 1 / result : result;
}

// Test cases
console.log(myPow(2.0, 10)); // 1024.0
console.log(myPow(2.1, 3));  // 9.261
console.log(myPow(2.0, -2)); // 0.25

Line Notes

if (n === 0) return 1.0;Return 1 for exponent zero immediately

let negative = n < 0;Flag to remember if exponent is negative

for (let i = 0; i < n; i++) {Multiply x by itself n times

return negative ? 1 / result : result;Invert result if exponent was negative

⏱

Complexity

TimeO(n)

SpaceO(1)

We multiply x by itself n times, so time grows linearly with n. Space is constant as no extra data structures are used.

💡 For n=20, this means 20 multiplications, which is manageable, but for n=100000, it means 100000 multiplications, which is slow.

Interview Verdict: TLE for large n

This approach is too slow for large exponents and will time out in interviews, but it is important to understand the baseline before optimizing.

🧠

Recursive Fast Exponentiation (Divide and Conquer)

💡 This approach improves efficiency by reducing the number of multiplications using recursion and the property that x^n = (x^(n/2))^2.

Intuition

Instead of multiplying x n times, recursively compute x^(n/2) and square it. If n is odd, multiply by x once more.

Algorithm

1. If n is zero, return 1.
2. If n is negative, convert to positive and invert result later.
3. Recursively compute half = myPow(x, n//2).
4. Square half to get half * half.
5. If n is odd, multiply by x once more.
6. Return the result, invert if original n was negative.

💡 The recursion and halving make it less obvious at first, but it reduces the problem size exponentially.

</>

Code

def myPow(x: float, n: int) -> float:
    if n == 0:
        return 1.0
    negative = n < 0
    n = abs(n)
    half = myPow(x, n // 2)
    if n % 2 == 0:
        result = half * half
    else:
        result = half * half * x
    return 1 / result if negative else result

# Driver code
if __name__ == '__main__':
    print(myPow(2.0, 10))  # 1024.0
    print(myPow(2.1, 3))   # 9.261
    print(myPow(2.0, -2))  # 0.25

Line Notes

if n == 0:Base case: any number to power 0 is 1

negative = n < 0Track if exponent is negative for inversion

half = myPow(x, n // 2)Recursive call to compute half power

if n % 2 == 0:Check if exponent is even or odd to decide multiplication

return 1 / result if negative else resultInvert result if original exponent was negative

public class Solution {
    public static double myPow(double x, int n) {
        if (n == 0) return 1.0;
        boolean negative = n < 0;
        long N = Math.abs((long)n);
        double half = myPowHelper(x, N);
        return negative ? 1 / half : half;
    }

    private static double myPowHelper(double x, long n) {
        if (n == 0) return 1.0;
        double half = myPowHelper(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }

    public static void main(String[] args) {
        System.out.println(myPow(2.0, 10)); // 1024.0
        System.out.println(myPow(2.1, 3));  // 9.261
        System.out.println(myPow(2.0, -2)); // 0.25
    }
}

Line Notes

if (n == 0) return 1.0;Base case for recursion

boolean negative = n < 0;Flag for negative exponent

double half = myPowHelper(x, N);Compute power recursively

if (n % 2 == 0)Check even/odd exponent to decide multiplication

return negative ? 1 / half : half;Invert result if original exponent was negative

#include <iostream>
#include <cmath>
using namespace std;

double myPowHelper(double x, long long n) {
    if (n == 0) return 1.0;
    double half = myPowHelper(x, n / 2);
    if (n % 2 == 0) {
        return half * half;
    } else {
        return half * half * x;
    }
}

double myPow(double x, int n) {
    if (n == 0) return 1.0;
    bool negative = n < 0;
    long long N = abs((long long)n);
    double result = myPowHelper(x, N);
    return negative ? 1 / result : result;
}

int main() {
    cout << myPow(2.0, 10) << endl; // 1024.0
    cout << myPow(2.1, 3) << endl;  // 9.261
    cout << myPow(2.0, -2) << endl; // 0.25
    return 0;
}

Line Notes

if (n == 0) return 1.0;Base case for recursion

double half = myPowHelper(x, n / 2);Recursive call to compute half power

if (n % 2 == 0)Check if exponent is even or odd

return negative ? 1 / result : result;Invert result if exponent was negative

function myPowHelper(x, n) {
    if (n === 0) return 1.0;
    let half = myPowHelper(x, Math.floor(n / 2));
    if (n % 2 === 0) {
        return half * half;
    } else {
        return half * half * x;
    }
}

function myPow(x, n) {
    if (n === 0) return 1.0;
    let negative = n < 0;
    n = Math.abs(n);
    let result = myPowHelper(x, n);
    return negative ? 1 / result : result;
}

// Test cases
console.log(myPow(2.0, 10)); // 1024.0
console.log(myPow(2.1, 3));  // 9.261
console.log(myPow(2.0, -2)); // 0.25

Line Notes

if (n === 0) return 1.0;Base case for recursion

let half = myPowHelper(x, Math.floor(n / 2));Recursive call to compute half power

if (n % 2 === 0)Check if exponent is even or odd

return negative ? 1 / result : result;Invert result if exponent was negative

⏱

Complexity

TimeO(log n)

SpaceO(log n) due to recursion stack

Each recursive call halves n, so the depth is log n. Multiplications per call are constant.

💡 For n=1024, this means about 10 multiplications instead of 1024, a huge speedup.

Interview Verdict: Accepted

This approach is efficient and accepted in interviews, but recursion stack depth can be a concern for very large n.

🧠

Iterative Fast Exponentiation (Binary Exponentiation)

💡 This approach optimizes further by eliminating recursion and using bit manipulation to compute powers efficiently.

Intuition

Use the binary representation of n to multiply x only when the corresponding bit is set, squaring x each iteration.

Algorithm

1. If n is zero, return 1.
2. If n is negative, convert to positive and invert result later.
3. Initialize result to 1 and current_product to x.
4. While n > 0, if the least significant bit of n is 1, multiply result by current_product.
5. Square current_product each iteration.
6. Right shift n by 1 bit.
7. Return result, inverted if original n was negative.

💡 This algorithm uses bitwise operations to reduce multiplications and avoid recursion, making it efficient and safe.

</>

Code

def myPow(x: float, n: int) -> float:
    if n == 0:
        return 1.0
    negative = n < 0
    n = abs(n)
    result = 1.0
    current_product = x
    while n > 0:
        if n % 2 == 1:
            result *= current_product
        current_product *= current_product
        n //= 2
    return 1 / result if negative else result

# Driver code
if __name__ == '__main__':
    print(myPow(2.0, 10))  # 1024.0
    print(myPow(2.1, 3))   # 9.261
    print(myPow(2.0, -2))  # 0.25

Line Notes

if n == 0:Handle zero exponent base case

negative = n < 0Track if exponent is negative

while n > 0:Loop until all bits of n are processed

if n % 2 == 1:Check if current bit is set to multiply result

current_product *= current_productSquare current_product to represent next power of two

public class Solution {
    public static double myPow(double x, int n) {
        if (n == 0) return 1.0;
        boolean negative = n < 0;
        long N = Math.abs((long)n);
        double result = 1.0;
        double currentProduct = x;
        while (N > 0) {
            if ((N & 1) == 1) {
                result *= currentProduct;
            }
            currentProduct *= currentProduct;
            N >>= 1;
        }
        return negative ? 1 / result : result;
    }

    public static void main(String[] args) {
        System.out.println(myPow(2.0, 10)); // 1024.0
        System.out.println(myPow(2.1, 3));  // 9.261
        System.out.println(myPow(2.0, -2)); // 0.25
    }
}

Line Notes

if (n == 0) return 1.0;Base case for zero exponent

boolean negative = n < 0;Flag for negative exponent

while (N > 0) {Process bits of exponent until zero

if ((N & 1) == 1)Check if least significant bit is set

currentProduct *= currentProduct;Square currentProduct to move to next power of two

return negative ? 1 / result : result;Invert result if exponent was negative

#include <iostream>
#include <cmath>
using namespace std;

double myPow(double x, int n) {
    if (n == 0) return 1.0;
    bool negative = n < 0;
    long long N = abs((long long)n);
    double result = 1.0;
    double currentProduct = x;
    while (N > 0) {
        if (N & 1) {
            result *= currentProduct;
        }
        currentProduct *= currentProduct;
        N >>= 1;
    }
    return negative ? 1 / result : result;
}

int main() {
    cout << myPow(2.0, 10) << endl; // 1024.0
    cout << myPow(2.1, 3) << endl;  // 9.261
    cout << myPow(2.0, -2) << endl; // 0.25
    return 0;
}

Line Notes

if (n == 0) return 1.0;Handle zero exponent base case

bool negative = n < 0;Track if exponent is negative

while (N > 0) {Loop over bits of exponent

if (N & 1)Check if current bit is set to multiply result

currentProduct *= currentProduct;Square currentProduct to move to next power of two

return negative ? 1 / result : result;Invert result if exponent was negative

function myPow(x, n) {
    if (n === 0) return 1.0;
    let negative = n < 0;
    n = Math.abs(n);
    let result = 1.0;
    let currentProduct = x;
    while (n > 0) {
        if ((n & 1) === 1) {
            result *= currentProduct;
        }
        currentProduct *= currentProduct;
        n >>= 1;
    }
    return negative ? 1 / result : result;
}

// Test cases
console.log(myPow(2.0, 10)); // 1024.0
console.log(myPow(2.1, 3));  // 9.261
console.log(myPow(2.0, -2)); // 0.25

Line Notes

if (n === 0) return 1.0;Return 1 for zero exponent

let negative = n < 0;Flag to track negative exponent

while (n > 0) {Process each bit of exponent

if ((n & 1) === 1)Multiply result if current bit is set

currentProduct *= currentProduct;Square currentProduct to move to next power of two

return negative ? 1 / result : result;Invert result if exponent was negative

⏱

Complexity

TimeO(log n)

SpaceO(1)

Each iteration halves n, so the loop runs in logarithmic time. Space is constant as no recursion is used.

💡 For n=1,000,000, this means about 20 multiplications, making it very efficient.

Interview Verdict: Accepted and optimal

This is the best practical solution for this problem, combining efficiency and safety by avoiding recursion.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the iterative fast exponentiation is the best choice to code due to its efficiency and safety. Brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(1)	No	N/A	Mention only - never code
2. Recursive Fast Exponentiation	O(log n)	O(log n) due to recursion stack	Yes (deep recursion)	N/A	Good to explain, but watch for stack overflow
3. Iterative Fast Exponentiation	O(log n)	O(1)	No	N/A	Best to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding. Progress to optimized solutions and discuss tradeoffs.

How to Present

Step 1: Clarify input types and constraints, including negative exponents.Step 2: State the brute force approach to show baseline understanding.Step 3: Introduce recursive fast exponentiation to improve efficiency.Step 4: Present iterative binary exponentiation as the optimal solution.Step 5: Discuss edge cases and test your code with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of exponentiation properties, ability to optimize naive solutions, handle edge cases, and write clean, efficient code.

Common Follow-ups

• How would you handle very large exponents beyond 32-bit integer range? → Use 64-bit integer or BigInteger types.
• Can you modify the code to compute modulo powers efficiently? → Incorporate modulo operations during multiplication.

💡 These follow-ups test your ability to adapt the solution to real-world constraints like integer overflow and modular arithmetic.

🔍

Pattern Recognition

When to Use

1) You need to compute powers efficiently. 2) The exponent can be large. 3) The problem hints at divide and conquer or binary manipulation. 4) Constraints require better than linear time.

Signature Phrases

compute x raised to the power nfast exponentiationefficient power calculation

NOT This Pattern When

Problems that require simple multiplication or addition without exponentiation are not this pattern.

Similar Problems

Integer Power - basic power calculationModular Exponentiation - power with modulo to avoid overflow

Practice

1. Consider the following code snippet implementing the binary search on value range approach to find the median of two sorted arrays. Given nums1 = [1, 3] and nums2 = [2, 4], what is the final returned median?

easy

A. 2.0

B. 2.5

C. 3.0

D. 2.25

Solution

1. Step 1: Trace binary search iterations

   Initial left=1, right=4. Mid=2, countLessEqual(2)=3 ≥ 2.5 so right=2. Next mid=1, countLessEqual(1)=1 < 2.5 so left=2.

2. Step 2: Compute median for even total length

   Left=2, total length=4 (even). Candidates before 2 are nums1[0]=1 and nums2[0]=2, max=2. Median=(2+3)/2=2.5 is correct median of combined sorted array [1,2,3,4]. The code snippet's logic is incomplete but assuming correct logic, median is 2.5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Median of combined sorted array [1,2,3,4] is 2.5 [OK]

Hint: Median of [1,2,3,4] is average of 2 and 3 [OK]

Common Mistakes:

• Off-by-one in bisect boundaries
• Confusing left with median
• Ignoring even length median averaging

2. You are given an array of non-negative integers and a number m. You want to split the array into m non-empty continuous subarrays such that the largest sum among these subarrays is minimized. Which algorithmic approach guarantees finding this minimal largest sum efficiently?

easy

A. Dynamic programming with memoization over all possible splits

B. Greedy approach that always splits when the current sum exceeds a fixed threshold

C. Binary search on the answer space combined with a greedy feasibility check

D. Sorting the array and using two pointers to find the minimal largest sum

Solution

1. Step 1: Understand the problem constraints

   The problem requires minimizing the largest sum among m subarrays, which is a classic optimization problem over a numeric answer space.

2. Step 2: Identify the approach that efficiently searches the answer space

   Binary search on the possible sums combined with a greedy check to verify feasibility is the standard approach that guarantees optimality and efficiency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search on answer space is the canonical pattern for this problem [OK]

Hint: Minimize max sum -> binary search on answer space [OK]

Common Mistakes:

• Assuming greedy splitting always yields optimal solution
• Trying DP without pruning leads to exponential time
• Sorting does not help because order matters

3. What is the time complexity of counting occurrences of a target in a sorted array using binary search to find left and right boundaries?

medium

A. O(n) because you must scan the array to count

B. O(log n) because binary search halves the search space each step

C. O(log n * log n) because two binary searches are performed

D. O(1) because built-in functions are optimized

Solution

1. Step 1: Analyze binary search calls

   Two binary searches are performed independently, each O(log n).

2. Step 2: Combine complexities

   Total time is O(log n) + O(log n) = O(log n), since constants are ignored.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two binary searches do not multiply complexities [OK]

Hint: Two O(log n) calls sum to O(log n) [OK]

Common Mistakes:

• Confusing two calls as O(log n * log n)
• Assuming linear scan is needed
• Believing built-in functions run in O(1)

4. Examine the following buggy code that attempts to search a target in a 2D matrix using the staircase search approach starting from the top-left corner. Identify the line containing the subtle bug that causes incorrect behavior or infinite loops.

medium

A. Line 9: Incrementing row when element is less than target

B. Line 7: Using '<' instead of '<=' in while condition

C. Line 11: Decrementing col without boundary check

D. Line 3: Starting at top-left corner instead of top-right

Solution

1. Step 1: Analyze starting point

   Starting at top-left corner breaks the staircase search logic because we cannot eliminate rows or columns correctly.

2. Step 2: Check pointer movements

   Moving row down when current < target and col left when current > target only works if starting at top-right corner.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Starting at top-left causes infinite loops or wrong results [OK]

Hint: Staircase search must start at top-right corner [OK]

Common Mistakes:

• Starting at top-left or bottom-left corner
• Not checking empty matrix
• Moving pointers in wrong directions

5. Suppose the problem is modified so that packages can be shipped in any order (not necessarily the given order) within the given days. Which of the following approaches correctly finds the minimal ship capacity under this new constraint?

hard

A. Use dynamic programming to assign packages to days minimizing maximum load per day, combined with binary search on capacity

B. Sort packages in descending order and use a greedy bin-packing heuristic combined with binary search on capacity

C. Use a simple greedy approach assigning packages to days in any order without binary search

D. Use the same binary search on capacity with the original feasibility check since order doesn't matter

Solution

1. Step 1: Understand the relaxed constraint

   Packages can be shipped in any order, so the problem becomes a variant of multi-way partition or bin packing minimizing max load.

2. Step 2: Identify correct approach

   Binary search on capacity still applies, but feasibility check requires DP or backtracking to assign packages optimally to days, as greedy heuristics may fail.

3. Step 3: Why other options fail

   Original feasibility check assumes fixed order; greedy heuristics are approximate and may not find minimal capacity.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP feasibility check with binary search needed for unordered assignment [OK]

Hint: Order relaxation requires DP feasibility check, not simple greedy [OK]

Common Mistakes:

• Using original feasibility check ignoring order change
• Assuming greedy suffices
• Ignoring complexity increase