Pow(x,n) LeetCode Solution
Pow(x,n) LeetCode Solution :
Implement pow(x, n), which calculates x raised to the power n (i.e., xn).
The function Pow(x, n) is typically used to calculate the result of raising a number x to a given exponent n. In other words, it calculates the value of x raised to the power of n.
Example :
Input:x = 2.00000, n = 10
Output: 1024.00000
Pow(x,n) LeetCode Solution :
Constraints :
-100.0 < x < 100.0
-231 <= n <= 231-1
n is an integer.
Either x is not zero or n > 0.
-104 <= xn <= 104
Approach
The Approach used problem using binary exponentiation which reduces the time complexity to O(log n) from O(n). If n is negative, we convert it to positive and take the reciprocal of the base x. We then repeatedly square the base (stored in current_product) and reduce the power to half until the power becomes zero. If at any point, the power is odd, we multiply the result by current_product. The final result will be the answer.
Complexity :
Time complexity: The time complexity of our algorithm is (O(\log n)), as we are reducing the power to half in each step.
Space complexity:. The space complexity of our algorithm is (O(1)), as we are using only a constant amount of space.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code for Pow(x,n) LeetCode Solution : :
C++
Java
Python
C++
class Solution {
public:
double myPow(double x, long long n) {
if(n < 0) {
x = 1 / x;
n = -n;
}
double result = 1;
double current_product = x;
while(n > 0) {
if(n % 2 == 1) {
result = result * current_product;
}
current_product = current_product * current_product;
n = n / 2;
}
return result;
}
};
Java
class Solution {
public double myPow(double x, long n) {
if(n < 0) {
x = 1 / x;
n = -n;
}
double result = 1;
double current_product = x;
while(n > 0) {
if(n % 2 == 1) {
result = result * current_product;
}
current_product = current_product * current_product;
n = n / 2;
}
return result;
}
}
Python
class Solution:
def myPow(self, x: float, n: int) -> float:
if n < 0:
x = 1 / x
n = -n
result = 1
current_product = x
while n > 0:
if n % 2 == 1:
result = result * current_product
current_product = current_product * current_product
n = n // 2
return result
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment