Задача: 50. Pow(x, n)
Сложность: medium

Реализуйте функцию pow(x, n), которая вычисляет x, возведенное в степень n (то есть x^n).

Пример:

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

👨‍💻 Алгоритм:

1️⃣Создайте метод binaryExp, который принимает параметры x и n.
Если n равно 0, мы возвращаем 1.
Если n отрицательное, вычисляем результат, как если бы n было положительным, и возвращаем обратное значение, то есть 1 / binaryExp(x, -n). При этом -n может выйти за пределы диапазона целых чисел, поэтому n должно быть 64-битной целочисленной переменной.

2️⃣В противном случае, используя бинарное возведение в степень, мы уменьшаем показатель степени n вдвое и рекурсивно вычисляем и возвращаем результат после решения новой подзадачи, как обсуждалось ранее.

3️⃣Вызовите метод binaryExp(x, n) и верните результат.

😎 Решение:

function binaryExp(x, n) {
    if (n === 0) {
        return 1;
    }
    if (n < 0) {
        return 1 / binaryExp(x, -1 * n);
    }
    if (n % 2 === 1) {
        return x * binaryExp(x * x, (n - 1) / 2);
    } else {
        return binaryExp(x * x, n / 2);
    }
}

var myPow = function (x, n) {
    return binaryExp(x, n);
};

Ставь 👍 и забирай 📚 Базу знаний