Topic Description (Medium Difficulty)

It’s just exponentiating.

Method a

To exponents, the simplest way to think about it, is to write a for loop multiplicative.

And the negative power, for exampleWe can solve for it firstAnd then take the reciprocal,, will do.

double mul = 1;
if (n > 0) {
    for (int i = 0; i < n; i++) { mul *= x; }}else {
    n = -n;
    for (int i = 0; i < n; i++) {
        mul *= x;
    }
    mul = 1 / mul;
}
Copy the code

But that would be a problem. BeforeQuestion 29We talked about, the problem is that n equals minus n, because it’s the least negative numberIf I take the negative, it’s still, according to computer rules, zeroSo this situation needs to be discussed separately.

if (n == -2147483648) {
    return 0;
}
Copy the code

And, of course, to do that, we need to talk about negative 1 and 1 separately, because any power they raise to is either 1 or negative 1.

if (x == -1) {
    if ((n & 1) != 0) { // If the bit and does not equal 0, it is odd
        return -1;
    } else {
        return 1; }}if (x == 1.0)
    return 1;
Copy the code

So there you have it.

public double myPow(double x, int n) {
    if (x == -1) {
        if ((n & 1) != 0) {
            return -1;
        } else {
            return 1; }}if (x == 1.0)
        return 1;

    if (n == -2147483648) {
        return 0;
    }
    double mul = 1;
    if (n > 0) {
        for (int i = 0; i < n; i++) { mul *= x; }}else {
        n = -n;
        for (int i = 0; i < n; i++) {
            mul *= x;
        }
        mul = 1 / mul;
    }
    return mul;
}
Copy the code

Time complexity: O (n).

Space complexity: O (1).

Solution binary recursion

For the above solution, it’s too slow. We can optimize it. We’re doing something similar to problem 29. So instead of multiplying over and over again, when we get to the second power, we can just multiply the second power, and we’ll get to the fourth power, and then we’ll multiply the fourth power, and we’ll get to the eighth power, and that’ll be a lot faster.

Let’s just use the recursion

If n is even,.

If n is odd,.

public double powRecursion(double x, int n) {
    if (n == 0) {
        return 1;
    }
    // Even case
    if ((n & 1) = =0) { 
        double temp = powRecursion(x, n / 2);
        return temp * temp;
    } else { // odd numbers
        double temp = powRecursion(x, n / 2);
        returntemp * temp * x; }}public double myPow(double x, int n) {
    if (x == -1) {
        if ((n & 1) != 0) {
            return -1;
        } else {
            return 1; }}if (x == 1.0 f)
        return 1;

    if (n == -2147483648) {
        return 0;
    }
    double mul = 1;
    if (n > 0) {
        mul = powRecursion(x, n);
    } else {
        n = -n;
        mul = powRecursion(x, n);
        mul = 1 / mul;
    }
    return mul;
}
Copy the code

Time complexity: O (log (n)).

Space complexity:

Of course, there are other ways to do this recursion, see here.

The recursive idea is going to look something like this

For n is even.

, for n is odd,

The code is pretty easy to write.

public double powRecursion(double x, int n) {
    if (n == 0) {
        return 1;
    }
    // Even case
    if ((n & 1) = =0) { 
        return powRecursion(x * x, n / 2);
    } else { // odd numbers
        return powRecursion(x * x, n / 2) * x; }}public double myPow(double x, int n) {
    if (x == -1) {
        if ((n & 1) != 0) {
            return -1;
        } else {
            return 1; }}if (x == 1.0 f)
        return 1;

    if (n == -2147483648) {
        return 0;
    }
    double mul = 1;
    if (n > 0) {
        mul = powRecursion(x, n);
    } else {
        n = -n;
        mul = powRecursion(x, n);
        mul = 1 / mul;
    }
    return mul;
}
Copy the code

Time complexity: O (log (n)).

Space complexity:

Solution three iterations

Here is a new solution, at the beginning of the previous train of thought, has not understood. In the afternoon, I asked my classmates, who immediately thought of the solution they saw in “The Beauty of Programming”, and here to share.

Let’s take x to the tenth. The base 2 of 10 is 1010, and then we extend it to the sum of powers of 2 by converting base 2 to base 10.

In this case, if you look at the graph below, you can see the correspondence between them.

Base 2 is 1, 0, 1, 0, and we just multiply the ones that correspond to 1, and the ones that we multiply are very regular, and the first one is the product of the second one.. We can start iterating from the rightmost digit. Let’s look at the code.

public double myPow(double x, int n) {
    if (x == -1) {
        if ((n & 1) != 0) {
            return -1;
        } else {
            return 1; }}if (x == 1.0 f)
        return 1;

    if (n == -2147483648) {
        return 0;
    }
    double mul = 1;
    if (n > 0) {
        mul = powIteration(x, n);
    } else {
        n = -n;
        mul = powIteration(x, n);
        mul = 1 / mul;
    }
    return mul;
}

public double powIteration(double x, int n) {
    double ans = 1;
    // Iterate over each bit
    while (n > 0) {
        // The last digit is 1, added to the multiplicative result
        if ((n & 1) = =1) {
            ans = ans * x;
        }
        / / update the x
        x = x * x;
        // Move n to the right one bit
        n = n >> 1;
    }
    return ans;
}
Copy the code

Time complexity: log (n).

Space complexity: O (1).

The total

From the general method, to the recursion, to the final solution, directly in base 2, each number can be converted to a sum of powers of 2, and the final solution is achieved.

See Leetcode.Wang for more details on popular problems.