Practice/Meta/Leetcode 50. Pow(x, n)

Leetcode 50. Pow(x, n)

CodingMust

Problem

Implement a function that calculates x raised to the power of n, where x is a floating-point number and n is a signed 32-bit integer. Your solution must handle both positive and negative exponents efficiently.

The naive approach of multiplying x by itself n times would take O(n) time, which is too slow for large values of n. You need to implement an algorithm that runs in O(log |n|) time.

Requirements

1. Return x^n as a floating-point number
2. Handle negative exponents correctly (x^(-n) = 1/(x^n))
3. Handle the edge case where n is the minimum 32-bit integer (-2147483648)
4. Achieve O(log |n|) time complexity
5. Use O(log |n|) space complexity for the recursive approach or O(1) for iterative

Constraints

• -100.0 < x < 100.0
• -2^31 ≤= n ≤= 2^31 - 1
• x is not zero when n is negative
• The result will fit in a 64-bit floating-point number

Examples

Example 1:

Input: x = 2.0, n = 5 Output: 32.0 Explanation: 2 * 2 * 2 * 2 * 2 = 32

Example 2:

Input: x = 3.0, n = -2 Output: 0.11111 Explanation: 3^(-2) = 1/(3^2) = 1/9 ≈ 0.11111

Example 3:

Input: x = 2.0, n = -2147483648 Output: 0.0 Explanation: The result is so small it's effectively zero

Example 4:

Input: x = 1.0, n = 123456789 Output: 1.0 Explanation: 1 raised to any power is 1