50. Pow(x, n)

Problem Statement

link: https://leetcode.com/problems/powx-n/ https://leetcode.cn/problems/powx-n/

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

Example:

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

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

Input: x = 2.00000, n = -2 Output: 0.25000

Solution Approach

The solution leverages the properties of exponentiation and iteratively reduces the power to be computed by half, making use of the binary representation of the exponent.

Algorithm

1. Inversion for Negative Powers: If the power n is negative, invert the base x (i.e., calculate 1/x) and negate n to make it positive.
2. Iterative Power Reduction: While n is greater than 0, check if n is odd (i.e., n%2 is non-zero). If it is, multiply the result by x. Then, continuously reduce n by half (i.e., floor division by 2) and square x at each step.
3. Final Result: Return the accumulated result, which now represents x raised to the power n.

Implement

    class Solution:
      def myPow(self, x: float, n: int) -> float:
          if n < 0:
              x = 1 / x
              n = -n
          res = 1
          while n > 0:
              if n % 2 :
                  res *= x
              n //= 2
              x *= x
          return res

    
    

Twitter  facebook  Email