50. Pow(x, n)

Implement pow(x, n).

50. Pow(x, n)

Реализуйте pow(x, n).

// C++

class Solution {

public:

double myPow(double x, int n) {

}

};

// Java

public class Solution {

public double myPow(double x, int n) {

}

}

SOLUTION

recursion

Algorithm analysis

Let’s implement the power function with complexity O(log₂n), because for example if x = 1, n = 10⁹ the algorithm with linear complexity gives Time Limit Exceeded.

The degree n can be negative, in this case first evaluate temp = x^|n|, and return 1 / temp.

The degree must be converted to long long type. If n = -2147483648, the value -n does not fit in int.

РЕШЕНИЕ

рекурсия

Анализ алгоритма

Реализуем возведение в степень с оценкой O(log₂n), так как например при x = 1, n = 10⁹ линейная оценка не пройдет по времени.

Степень n может быть отрицательной, в таком случае сначала вычислим temp = x^|n|, и вернем 1 / temp.

Степень следует преобразовать в тип long long. Например, при n = -2147483648 значение -n уже не будет помещаться в int.

Реализация алгоритма

class Solution

{

public:

double Pow(double x, long long n)

{

if (n == 0) return 1;

if (n % 2 == 0)

{

double temp = Pow(x,n/2);

return temp * temp;

}

else

return x * Pow(x,n-1);

}

double myPow(double x, int n)

{

int sign = (n >= 0) ? 1 : -1;

long long nn = n;

if (nn < 0) nn = -nn;

double temp = Pow(x,nn);

if (sign < 0) temp = 1 / temp;

return temp;

}

};

Java реализация

public class Solution

{

public double Pow(double x, long n)

{

if (n == 0) return 1;

if (n % 2 == 0)

return Pow(x*x,n/2);

else

return x * Pow(x,n-1);

}

double myPow(double x, int n)

{

int sign = (n >= 0) ? 1 : -1;

long nn = n; // if n = -2147483648, -n does not fit in int

if (nn < 0) nn = -nn;

double temp = Pow(x,nn);

if (sign < 0) temp = 1 / temp;

return temp;

}

}