Pow(x, n) - Fast Exponentiation

📋

Problem

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

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

Edge cases: 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)

</>

IDE

def myPow(x: float, n: int) -> float:public double myPow(double x, int n)double myPow(double x, int n)function myPow(x, n)

def myPow(x: float, n: int) -> float:
    # Write your solution here
    pass

class Solution {
    public double myPow(double x, int n) {
        // Write your solution here
        return 0.0;
    }
}

#include <vector>
using namespace std;

double myPow(double x, int n) {
    // Write your solution here
    return 0.0;
}

function myPow(x, n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0.0 for n=0Missing base case for n=0, returning 0 instead of 1.✅ Add if n == 0: return 1.0 at the start of the function.

Wrong: Negative powers computed as zero or errorNot handling negative exponent by inverting base and using positive exponent.✅ If n < 0, set negative = True, n = abs(n), then return 1/result after computation.

Wrong: Overflow or infinite loop for n = -2147483648Negating Integer.MIN_VALUE causes overflow; abs(n) overflows int range.✅ Use 64-bit integer type for exponent or handle n == Integer.MIN_VALUE as special case.

Wrong: Timeout or incorrect result for large n (e.g., 100000)Using naive O(n) multiplication instead of O(log n) binary exponentiation.✅ Implement binary exponentiation using recursion or iteration to reduce time complexity.

Wrong: Incorrect result for zero base and positive exponentNot returning 0 immediately when x == 0 and n > 0, causing division by zero or wrong output.✅ Add check: if x == 0 and n > 0: return 0.0.

✓

Test Cases

Make sure your code handles zero and one exponents correctly before moving on.

Test your code with negative and extreme exponent values to catch edge bugs.

Optimize your solution to run in logarithmic time to handle large inputs efficiently.

t1_01basic

Input{"x":2,"n":10}

Expected1024

⏱ Performance - must finish in 2000ms

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

💡 Think about how to reduce the number of multiplications using divide and conquer.

💡 Use binary exponentiation: split n into halves recursively.

💡 Implement dp or recursion: pow(x, n) = pow(x, n//2)^2, multiply by x if n is odd.

Why it failed: Basic case failed - likely incorrect handling of positive powers or missing fast exponentiation logic. Fix by implementing binary exponentiation correctly.

✓ Core logic for positive powers and fast exponentiation is correct.

t1_02basic

Input{"x":2.1,"n":3}

Expected9.261000000000001

⏱ Performance - must finish in 2000ms

2.1^3 = 2.1 * 2.1 * 2.1 = 9.261

💡 Check multiplication order and precision for floating point numbers.

💡 Use recursive or iterative fast exponentiation to reduce multiplications.

💡 Ensure multiplication accumulates correctly and returns float.

Why it failed: Incorrect multiplication or floating point handling caused wrong output. Fix by careful multiplication and returning float result.

✓ Correctly computes power for positive integer exponent with floating point base.

t2_01edge

Input{"x":2,"n":0}

Expected1

⏱ Performance - must finish in 2000ms

Any number to the power 0 is 1

💡 Remember the mathematical rule for zero exponent.

💡 Check if your code explicitly handles n == 0 case.

💡 Return 1.0 immediately when n is zero.

Why it failed: Failed to handle n=0 case, returning wrong value. Fix by adding if n == 0: return 1.0.

✓ Correctly returns 1.0 for zero exponent.

t2_02edge

Input{"x":2,"n":1}

Expected2

⏱ Performance - must finish in 2000ms

Any number to the power 1 is the number itself

💡 Check if your code handles n=1 as a base case.

💡 Avoid unnecessary recursion or loops when n=1.

💡 Return x immediately when n is one.

Why it failed: Failed to handle n=1 case, possibly overcomplicating or returning wrong value. Fix by returning x when n == 1.

✓ Correctly returns x for exponent 1.

t2_03edge

Input{"x":2,"n":-1}

Expected0.5

⏱ Performance - must finish in 2000ms

Negative exponent means reciprocal: 2^-1 = 1/2 = 0.5

💡 Negative powers invert the base: pow(x, -n) = 1 / pow(x, n).

💡 Check if your code handles negative n by converting to positive and inverting result.

💡 Implement logic: if n < 0, compute pow(x, -n) then return 1/result.

Why it failed: Failed to handle negative exponent correctly, returning wrong value or error. Fix by inverting base and using positive exponent.

✓ Correctly computes reciprocal for negative exponent.

t3_01corner

Input{"x":0,"n":5}

Expected0

⏱ Performance - must finish in 2000ms

Zero to positive power is zero: 0^5 = 0

💡 Check behavior when base x is zero and exponent positive.

💡 Avoid division by zero or incorrect handling of zero base.

💡 Return 0.0 immediately if x == 0 and n > 0.

Why it failed: Incorrect handling of zero base with positive exponent, possibly causing division by zero or wrong output. Fix by returning 0.0 when x == 0 and n > 0.

✓ Correctly returns 0.0 for zero base with positive exponent.

t3_02corner

Input{"x":2,"n":-2147483648}

Expected0

⏱ Performance - must finish in 2000ms

Minimum 32-bit int exponent: pow(2, -2147483648) is effectively 0 due to large negative power

💡 Handle edge case where n is Integer.MIN_VALUE (-2^31).

💡 Avoid overflow when negating n (abs(n) overflows).

💡 Use long or 64-bit integer to store abs(n) or handle n == Integer.MIN_VALUE separately.

Why it failed: Failed to handle Integer.MIN_VALUE negation causing overflow or infinite loop. Fix by using long type or special case for n == Integer.MIN_VALUE.

✓ Correctly handles minimum integer exponent without overflow.

t3_03corner

Input{"x":1.00001,"n":100000}

Expected2.7182682371975284

⏱ Performance - must finish in 2000ms

Testing precision and performance for large exponent with base close to 1

💡 Check for floating point precision loss in repeated multiplication.

💡 Use fast exponentiation to reduce multiplications and improve precision.

💡 Avoid naive loop; implement binary exponentiation for large n.

Why it failed: Naive multiplication causes TLE or precision loss. Fix by implementing binary exponentiation to handle large n efficiently.

✓ Efficiently computes large powers with good precision.

t4_01performance

Input{"x":1.00001,"n":100000}

Expectednull

⏱ Performance - must finish in 2000ms

Large exponent n=100000 tests O(log n) complexity; naive O(n) will TLE

💡 Naive multiplication is O(n) and too slow for large n.

💡 Use binary exponentiation to achieve O(log n) time complexity.

💡 Implement iterative or recursive fast exponentiation to pass performance test.

Why it failed: TLE due to O(n) naive multiplication approach. Fix by implementing O(log n) binary exponentiation.

✓ Algorithm runs in O(log n) time and passes performance constraints.

Practice

1. Consider the following recursive binary search code for finding the insert position of target = 2 in nums = [1, 3, 5, 6]. What is the final returned value?

easy

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace binary_search(0, 3)

   mid = (0+3)//2 = 1, nums[1] = 3 > 2, recurse left: binary_search(0, 0)

2. Step 2: Trace binary_search(0, 0)

   mid = (0+0)//2 = 0, nums[0] = 1 < 2, recurse right: binary_search(1, 0)

3. Step 3: Base case binary_search(1, 0)

   left > right, return left = 1 as insertion index

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Target 2 fits between 1 and 3 at index 1 [OK]

Hint: Follow recursive calls and base case carefully [OK]

Common Mistakes:

• Returning right instead of left at base case
• Off-by-one in mid calculation
• Confusing left and right updates

2. Consider the following Python code implementing the optimal solution for splitting an array into m subarrays minimizing the largest sum. Given nums = [7, 2, 5, 10] and m = 2, what is the final returned value?

easy

A. 10

B. 12

C. 17

D. 15

Solution

1. Step 1: Calculate prefix sums

   prefix = [0, 7, 9, 14, 24]

2. Step 2: Binary search on answer space [7,24]

   Check mid=15: can split into subarrays with max sum ≤15? Yes (e.g., [7,2,5] and [10]). Try lower mid=11: cannot split into 2 subarrays with max sum ≤11. Finally, minimal largest sum found is 12.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Minimal largest sum for splitting [7,2,5,10] into 2 parts is 12 [OK]

Hint: Trace binary search mid and feasibility check carefully [OK]

Common Mistakes:

• Off-by-one in bisect leading to wrong subarray boundaries
• Confusing max element with sum for low/high bounds
• Miscounting number of splits in feasibility check

3. Consider the following buggy code snippet for searching a target in a rotated sorted array with duplicates. Which line contains the subtle bug that can cause infinite loops or incorrect results?

medium

A. Line 9: if nums[mid] == target: return True

B. Line 7: mid = (left + right) // 2

C. Line 13: if nums[left] <= target < nums[mid]: right = mid - 1

D. Line 4: while left < right and nums[left] == nums[left + 1]: left += 1

Solution

1. Step 1: Identify duplicate skipping logic

   The code only skips duplicates from the left side, ignoring duplicates on the right side.

2. Step 2: Understand impact of skipping duplicates only on one side

   If duplicates exist on the right side, pointers may not move correctly, causing infinite loops or incorrect search decisions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Skipping duplicates only on one side breaks correctness [OK]

Hint: Must skip duplicates from both ends to avoid infinite loops [OK]

Common Mistakes:

• Skipping duplicates only from left or right
• Not checking target at mid first
• Incorrect pointer updates

4. Suppose the problem is modified so that the array can be rotated multiple times and may contain negative numbers as well as duplicates. Which modification to the algorithm is necessary to still find the minimum efficiently?

hard

A. Use the same modified binary search without changes, as negative numbers do not affect the logic.

B. Add an early exit check to return nums[low] if the subarray is already sorted before proceeding with binary search steps.

C. Switch to a brute force linear scan since multiple rotations and negatives break binary search assumptions.

D. Replace the high decrement step with incrementing low to handle duplicates better.

Solution

1. Step 1: Consider impact of negatives and multiple rotations

   Negative numbers do not affect the ordering logic; multiple rotations still produce a rotated sorted array.

2. Step 2: Importance of early exit

   Early exit when subarray is sorted avoids unnecessary binary search steps, improving efficiency especially with duplicates and negatives.

3. Step 3: Why other options fail

   Brute force is inefficient; incrementing low instead of decrementing high breaks correctness; unchanged algorithm misses optimization.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Early exit optimizes search in sorted subarrays [OK]

Hint: Early exit on sorted subarray improves efficiency [OK]

Common Mistakes:

• Assuming negatives break binary search
• Ignoring early exit optimization

5. Suppose now you want to make bouquets but flowers can be reused multiple times (i.e., each flower can be counted multiple times for different bouquets). Which modification to the algorithm is correct?

hard

A. Keep the same binary search and feasibility check, but remove resetting flowers count to zero on encountering a flower that blooms after the day.

B. Binary search is no longer applicable; instead, use a greedy approach to pick flowers repeatedly until bouquets are formed.

C. Use binary search on days, but feasibility must count bouquets by grouping any flowers bloomed by day, allowing reuse by not resetting flowers count.

D. Modify feasibility to count total flowers bloomed by day and check if total flowers >= m * k, ignoring adjacency.

Solution

1. Step 1: Understand reuse changes adjacency constraint

   If flowers can be reused multiple times, adjacency no longer matters; only total count of bloomed flowers by day matters.

2. Step 2: Modify feasibility check

   Feasibility reduces to checking if total bloomed flowers by day >= m * k, ignoring adjacency and resetting.

3. Step 3: Binary search remains valid

   Binary search on days still applies, but feasibility is simplified to total count check.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Counting total bloomed flowers matches reuse scenario. [OK]

Hint: Reuse removes adjacency; feasibility counts total bloomed flowers [OK]

Common Mistakes:

• Ignoring adjacency but still resetting flowers count
• Removing binary search unnecessarily