{x}
blog image

Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

 

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

 

Constraints:

  • -100.0 < x < 100.0
  • -231 <= n <= 231-1
  • n is an integer.
  • Either x is not zero or n > 0.
  • -104 <= xn <= 104

Solution Explanation: 50. Pow(x, n)

This problem asks to implement the pow(x, n) function, which calculates x raised to the power n (xn). A naive approach would involve multiplying x by itself n times, resulting in O(n) time complexity. However, a significantly more efficient solution exists using the concept of fast powering (also known as binary exponentiation).

Fast Powering Algorithm:

The core idea is to exploit the binary representation of the exponent n. We can express n as a sum of powers of 2:

n = bk2k + bk-12k-1 + ... + b121 + b020

where each bi is either 0 or 1. This allows us to calculate xn as:

xn = x(bk2k + bk-12k-1 + ... + b020) = xbk2k * xbk-12k-1 * ... * xb020

We can calculate these terms efficiently by repeatedly squaring x. If bi is 1, we multiply the result by the corresponding power of x.

Algorithm Steps:

  1. Handle Negative Exponent: If n is negative, we calculate x-n and take its reciprocal (1 / x-n).
  2. Iterative Squaring: We initialize the result ans to 1. We iterate through the bits of n from the least significant bit (LSB) to the most significant bit (MSB).
  3. Bitwise Check: In each iteration, we check if the current bit (n & 1) is 1. If it is, we multiply ans by the current power of x.
  4. Squaring: We square x in each iteration to get the next higher power of x.
  5. Right Shift: We right-shift n (n >>= 1) to move to the next bit.
  6. Return Result: After iterating through all bits, ans will hold the result xn.

Time and Space Complexity:

  • Time Complexity: O(log n) - The algorithm iterates through the bits of n, which is proportional to log2n.
  • Space Complexity: O(1) - The algorithm uses a constant amount of extra space.

Code Examples (Python, Java, C++, Go, TypeScript, Rust, JavaScript, C#):

The code examples in various languages provided in the original response demonstrate the implementation of the fast powering algorithm. They all follow the steps described above, efficiently calculating xn in logarithmic time. Note that the handling of negative exponents and the use of bitwise operations are key to the efficiency of these solutions. The qpow helper function encapsulates the core fast powering logic.

Example Usage:

For example, if x = 2 and n = 10, the algorithm would proceed as follows:

| n | n & 1 | x | ans | |---------|--------|---------|---------| | 10 | 0 | 2 | 1 | | 5 | 1 | 4 | 4 | | 2 | 0 | 16 | 4 | | 1 | 1 | 256 | 1024 | | 0 | 0 | 65536 | 1024 |

The final result, 1024, is correctly calculated. For negative exponents, the reciprocal is taken after calculating the positive power.