Katkat
Back

Implement Fast Power with Negative Exponents

LinkedInSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to implement the exponentiation by squaring algorithm while correctly handling edge cases like negative exponents and integer overflow.

Problem Statement

Implement a function myPow(base: float, exponent: int) -> float that calculates base raised to the power of exponent (base^exponent). You are not permitted to use built-in library functions like math.pow or the operator **.

Constraints

  • exponent is a 32-bit signed integer (-2^31 <= exponent <= 2^31 - 1).
  • base is a floating-point number.
  • Your solution must perform in O(log n) time complexity.

Examples

Example 1: Input: base = 2.0, exponent = 10 Output: 1024.0

Example 2: Input: base = 2.1, exponent = 3 Output: 9.261

Example 3: Input: base = 2.0, exponent = -2 Output: 0.25 (Calculation: 1 / (2^2) = 1 / 4 = 0.25)

Edge Cases to Consider

  • exponent = 0 (should return 1.0)
  • exponent is the minimum 32-bit integer (-2147483648). Converting this to a positive integer directly will cause overflow in many languages.
  • base = 0 or base = 1.

Hints

Hint 1

Consider the recursive relationship: x^n = x^(n/2) * x^(n/2) if n is even, and x * x^(n-1) if n is odd.

Hint 2

For negative exponents, remember that x^(-n) is equivalent to (1/x)^n.

Hint 3

When handling the minimum 32-bit integer, consider using a 64-bit integer type for the exponent to avoid overflow, or perform one extra multiplication step to reduce the magnitude safely.

Follow-up questions

  • How would you modify your algorithm if the exponent could be an extremely large number represented as a string?
  • What are the precision issues associated with floating-point exponentiation, and how might you mitigate them if high precision is required?
  • Can you implement this iteratively to avoid the stack space usage of recursion?