Возведение числа в степень. Имплементация функции pow(x, n)

Иногда, на алгоритмических секциях могут попросить реализовать какую-нибудь стандартную функцию любого языка, не используя встроенные функции. Например, это может быть функция сортировки массива, или, как в данном случае — функция возведения числа в степень. На leetcode эта задача помечена как medium, хотя, на мой взгляд, ничего сложного в ней нет. Во всяком случае в такой формулировке и с такими ограничениями.

Сложность: 🟠 Cредняя

ℹ️ Описание

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

⚠️ Ограничения

🔹Число x в диапазоне [-100.0, 100.0]
🔹Степень n в диапазоне [-2^31, (2^31) - 1]
🔹n - целое число
🔹Если x == 0, то n > 0
🔹Итоговый результат в диапазоне [-10000, 10000]


1️⃣ Пример

Входящие данные: x=2.00, n=10
Ответ: 1024

2️⃣ Пример

Входящие данные: x=2.10, n=3
Ответ: 9.261

3️⃣ Пример

Входящие данные: x=2.00, n=-2
Ответ: 0.25


✅ Решение

Для того, чтобы получить опимальное решение нужно:

- Вспомнить что такое рекурсивные функции и как с ними работать
- Свойство степеней: x^n = (x*x)^(n/2)
- Свойство степеней: x^(-n) = 1/ x^n

Алгоритм рекурсивной функции powAbsN(x, |n|).
|n| - модуль числа, то есть без учета знака.

Кейсы с отрицательной степенью обработаем отдельно, поделив 1 на pow(x, |n|):

🔘 Если n == 0, возвращаем 1 (x^0 всегда равен 1)

🔘 Если n == 1, возвращаем x

🔘 Если n четное число, возвращаем результат рекурсивного вызова функции, передав в качестве аргумента x квадрат от текущего значения x (x*x), а в качестве n - результат деления без остатка текущего значения n (n/2) - 2^4 = (2*2)^(4/2) = 4^2

🔘 Если n нечетное число, возвращаем результат рекурсивного вызова функции (также передав в качестве аргумента x квадрат от текущего значения x (x*x), а в качестве n - результат деления без остатка текущего значения n (n/2)) умноженый на текущее значение x - 2^5 = (2^4)*2 = (4^2)*2


Алгоритм основной функции myPow(x, n):

🔘 Если x == 1, возвращаем 1 (1 в любой степени равна 1)

🔘 Если x == -1, возвращаем -1 при нечетном n и 1 при четном n

🔘 Если n >= 0, возвращаем результат функции powAbsN(x, |n|)

🔘 Если n < 0, возвращаем 1/powAbsN(x, |n|)

Посмотреть реализацию

🅾️ Оценка сложности

По времени
Благодаря свойству степеней: x^n = (x*x)^(n/2), вместо n умножений числа x, на каждой итерации рекурсии мы сокращаем количество умножений в два раза. То есть сложность — O(log(n))


По памяти
Доп память константна — O(1)

#float #medium