Question

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

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

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/2² = 1/4 = 0.25

Constraints:

-100.0 < x < 100.0
-2³¹ <= n <= 2³¹-1
n is an integer.
-10⁴ <= xⁿ <= 10⁴

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

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;
	        }
	    }
	}
}

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

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return n >= 0 ? qmi(x, N) : 1.0 / qmi(x, -N);
    }

    private double qmi(double a, long k) {
        double res = 1;
        while (k != 0) {
            if ((k & 1) != 0) {
                res *= a;
            }
            a *= a;
            k >>= 1;
        }
        return res;
    }
}

// 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

func myPow(x float64, n int) float64 {
	if n >= 0 {
		return qmi(x, n)
	}
	return 1.0 / qmi(x, -n)
}

func qmi(a float64, k int) float64 {
	var res float64 = 1
	for k != 0 {
		if k&1 == 1 {
			res *= a
		}
		a *= a
		k >>= 1
	}
	return res
}

function myPow(x: number, n: number): number {
    return n >= 0 ? qmi(x, n) : 1 / qmi(x, -n);
}

function qmi(a: number, k: number): number {
    let res = 1;
    while (k) {
        if (k & 1) {
            res *= a;
        }
        a *= a;
        k >>>= 1;
    }
    return res;
}

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
    return n >= 0 ? qmi(x, n) : 1 / qmi(x, -n);
};

function qmi(a, k) {
    let res = 1;
    while (k) {
        if (k & 1) {
            res *= a;
        }
        a *= a;
        k >>>= 1;
    }
    return res;
}

public class Solution {
    public double MyPow(double x, int n) {
        long N = n;
        return n >= 0 ? qmi(x, N) : 1.0 / qmi(x, -N);
    }

    private double qmi(double a, long k) {
        double res = 1;
        while (k != 0) {
            if ((k & 1) != 0) {
                res *= a;
            }
            a *= a;
            k >>= 1;
        }
        return res;
    }
}

impl Solution {
    #[allow(dead_code)]
    pub fn my_pow(x: f64, n: i32) -> f64 {
        let mut x = x;
        let n = n as i64;
        if n >= 0 {
            Self::quick_pow(&mut x, n)
        } else {
            1.0 / Self::quick_pow(&mut x, -n)
        }
    }

    #[allow(dead_code)]
    fn quick_pow(x: &mut f64, mut n: i64) -> f64 {
        // `n` should greater or equal to zero
        let mut ret = 1.0;
        while n != 0 {
            if n & 0x1 == 1 {
                ret *= *x;
            }
            *x *= *x;
            n >>= 1;
        }
        ret
    }
}

50 - Pow(x, n)

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions