Question

Formatted question description: https://leetcode.ca/all/50.html

50	Pow(x, n)

Implement pow(x, n).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

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


Note:
    -100.0 < x < 100.0
    n is a 32-bit signed integer, within the range [−231, 231 − 1]

Algorithm

Use recursion to calculate in half, reduce n by half each time, so that n will eventually be reduced to 0, and any number to the power of 0 will be 1. At this time, multiply it back.

If n is even at this time, directly recurse the last time The obtained value can be returned as a square. If it is an odd number, it needs to be multiplied by the value of x.

Another thing to note is that n may be negative. For the case where n is negative, I can use its absolute value to calculate a result and then take its reciprocal. It was possible before, but now it’s added in the test case After a minus 2 to the 31st power, this will not work, because its absolute value exceeds the integer maximum value, there will be an overflow error, but you can use another way to write only one function, and handle n in each recursion. And then do the corresponding transformation.

Code

Java

public class Pow_x_n {

	public class Solution_recursion {
	    public double myPow(double x, int n) {

	        // return Math.pow(x, n);

	        double flag = 1;

	        if (x < 0 && n % 2 == 1) {
	            flag = -1;
	            x = x * (-1);
	        }

	        if (n == 0) {
	            return 1;
	        } else if (n > 0) {
	            double result = dfs(x, (long)n);
	            return result * flag;

	        } else {
	            // @note: below n*-1 already flowed... (1.00000,-2147483648)
	            // double result = dfs(x, (long)(n * (-1)));
	            double result = dfs(x, (long)n * (-1));
	            return (1 / result) * flag;
	        }
	    }

	    // @note: overflowed by input: (1.00000,-2147483648)
	    // private double dfs(double x, int n) {
	    private double dfs(double x, long n) {

	        if (n == 1) {
	            return x;
	        }

	        double half = dfs(x, n / 2);

	        if (n % 2 == 0) {
	            return half * half;
	        } else {
	            return x * half * half;
	        }
	    }
	}
}

// OJ: https://leetcode.com/problems/powx-n/
// Time: O(logN)
// Space: O(logN)
class Solution {
    double myPow(double x, long n) {
        if (n < 0) return 1 / myPow(x, -n);
        if (n == 0) return 1;
        if (n == 1) return x;
        if (n == 2) return x * x;
        return myPow(myPow(x, n / 2), 2) * (n % 2 ? x : 1);
    }
public:
    double myPow(double x, int n) {
        return myPow(x, (long)n);
    }
};

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def qmi(a, k):
            res = 1
            while k:
                if k & 1:
                    res *= a
                a *= a
                k >>= 1
            return res

        return qmi(x, n) if n >= 0 else 1 / qmi(x, -n)

############

class Solution(object):
  def myPow(self, x, n):
    """
    :type x: float
    :type n: int
    :rtype: float
    """
    if n < 0:
      n = -n
      x = 1 / x
    ans = 1
    while n:
      if n & 1:
        ans *= x
      x *= x
      n >>= 1
    return ans

50 - Pow(x, n)

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions