Pow(x, n) solution and explanation
Google
TCS
Infosys
9 more videos on this problem
POW(x,n) | Binary Exponentiation | Leetcodetake U forward · 8:10 · 401K views
Pow(x, n) - X to the power of N - Leetcode 50 - PythonNeetCode · 12:37 · 121K views
Binary Exponentiation | Pow(x,n) | Leetcode #50Techdose · 10:09 · 14K views
POW(X, N) | LEETCODE # 50 | PYTHON SOLUTIONCracking FAANG · 11:05 · 5K views
50. Pow(x, n) #leetcode | Beats 100% solutions | Easy solution using java| #codinginterviewquestionsGoCoderGo · 6:27 · 3K views
Leetcode 50 pow(x, n) Solution | Power of any number using javaLaxman G · 7:35 · 2K views
Leetcode 50. Pow(x, n)Jeevan Kumar - Cracckify · 4:55 · 1K views
Pow(x, n) | LeetCode 50 Fast ExponentiationDestination FAANG · 8:50 · 666 views
Pow(x, n) Python Solution - LeetCode #50Professor Oakes · 5:15 · 324 views
50. Pow(x, n) | #LeetCode Daily Challenge | C++ Recursive Solution | Exponentiation | 24 July 2023The Khurapaati Mind · 3:32 · 305 views
The problem
Implement pow(x, n), which calculates x raised to the power n (i.e., xn).
Example 1:
Input: x = 2.00000, n = 10 Output: 1024.00000
Example 2:
Input: x = 2.10000, n = 3 Output: 9.26100
Example 3:
Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25
Constraints:
-100.0 < x < 100.0-231 <= n <= 231-1nis an integer.- Either
xis not zero orn > 0. -104 <= xn <= 104
Approach overview
Problem Overview: The task is to implement pow(x, n), which returns x raised to the power n. The challenge comes from handling very large exponents efficiently, including negative values of n, without relying on built‑in power functions.
Approach 1: Naive Multiplication (O(n) time, O(1) space)
The most straightforward solution multiplies x by itself n times. You iterate from 1 to n, repeatedly updating the result with result *= x. For negative powers, compute 1 / x^|n|. This approach works but becomes extremely slow for large exponents because it performs one multiplication per step. It demonstrates the basic idea but fails typical interview constraints where n may be up to billions.
Approach 2: Iterative Exponentiation by Squaring (O(log n) time, O(1) space)
This optimized approach repeatedly squares the base while halving the exponent. The key observation is that x^n can be written as (x^2)^(n/2) when n is even, and x * x^(n-1) when n is odd. Using this property, you iterate while n > 0, multiply the result when the current bit of the exponent is odd, then square the base and divide the exponent by two. Because the exponent shrinks by half each step, the algorithm runs in logarithmic time. This method relies on simple arithmetic operations and fits naturally within topics like math and efficient power computation.
Approach 3: Recursive Divide and Conquer (O(log n) time, O(log n) space)
The recursive version applies the same exponentiation by squaring logic but expresses it using recursion. If n is even, compute pow(x, n/2) once and square the result. If n is odd, multiply x with the result of pow(x, n-1). The recursion depth is proportional to log n because the exponent is halved each time. The algorithm is clean and closely reflects the mathematical recurrence, making it a common teaching example in recursion and divide and conquer strategies. The tradeoff is additional call stack space compared to the iterative solution.
Recommended for interviews: Interviewers typically expect exponentiation by squaring. Start by explaining the naive multiplication approach to show baseline reasoning, then move to the logarithmic solution. The iterative implementation is usually preferred because it avoids recursion overhead while maintaining O(log n) time and constant space.
Approach 1: Iterative Method with Exponentiation by Squaring
The iterative method with exponentiation by squaring is an efficient way to calculate powers. It reduces the time complexity by squaring the base and halving the power at each step. This method leverages the mathematical property that xn = (x2)n/2 when n is even and xn = x * xn - 1 when n is odd. By iteratively updating the base and reducing the power, this method achieves a logarithmic time complexity.
class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1
N = n
if N < 0:
x = 1 / x
N = -N
result = 1
while N != 0:
if N % 2 != 0:
result *= x
x *= x
N //= 2
return result
sol = Solution()
print(sol.myPow(2.00000, 10))
print(sol.myPow(2.10000, 3))
print(sol.myPow(2.00000, -2))public class Solution {
public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double result = 1;
while (N != 0) {
if (N % 2 != 0) {
result *= x;
}
x *= x;
N /= 2;
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.myPow(2.00000, 10));
System.out.println(sol.myPow(2.10000, 3));
System.out.println(sol.myPow(2.00000, -2));
}
}#include <iostream>
class Solution {
public:
double myPow(double x, int n) {
long long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double result = 1;
while (N) {
if (N % 2 == 1) {
result *= x;
}
x *= x;
N /= 2;
}
return result;
}
};
int main() {
Solution sol;
std::cout << sol.myPow(2.00000, 10) << std::endl;
std::cout << sol.myPow(2.10000, 3) << std::endl;
std::cout << sol.myPow(2.00000, -2) << std::endl;
return 0;
}function myPow(x, n) {
let N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
let result = 1;
while (N !== 0) {
if (N % 2 !== 0) {
result *= x;
}
x *= x;
N = Math.floor(N / 2);
}
return result;
}
console.log(myPow(2.00000, 10));
console.log(myPow(2.10000, 3));
console.log(myPow(2.00000, -2));#include <stdio.h>
double myPow(double x, int n) {
long long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double result = 1;
while (N) {
if (N % 2 == 1) {
result *= x;
}
x *= x;
N /= 2;
}
return result;
}
int main() {
printf("%f\n", myPow(2.00000, 10));
printf("%f\n", myPow(2.10000, 3));
printf("%f\n", myPow(2.00000, -2));
return 0;
}using System;
public class Solution {
public double MyPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double result = 1;
while (N != 0) {
if ((N & 1) == 1) {
result *= x;
}
x *= x;
N >>= 1;
}
return result;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.MyPow(2.00000, 10));
Console.WriteLine(sol.MyPow(2.10000, 3));
Console.WriteLine(sol.MyPow(2.00000, -2));
}
}The Python solution handles negative powers by adjusting the base and uses integer division to halve the power in each iteration. Python's native floating-point operations simplify handling the precision required for real-number computations.
Time Complexity: O(log n), Space Complexity: O(1)
Approach 2: Recursive Divide and Conquer
The recursive divide and conquer method further optimizes power calculation by dividing the problem into smaller subproblems. By recursively dividing the power by 2, this approach minimizes the number of multiplications. If the power is even, it computes (xn/2)2, and if odd, it adjusts with an additional multiplication. This recursive approach can be more intuitive, especially for understanding the problem breakdown.
class Solution:
def myPow(self, x: float, n: int) -> float:
def myPowUtil(x, n):
if n == 0:
return 1
half = myPowUtil(x, n // 2)
if n % 2 == 0:
return half * half
else:
return half * half * x
if n < 0:
x = 1 / x
n = -n
return myPowUtil(x, n)
sol = Solution()
print(sol.myPow(2.00000, 10))
print(sol.myPow(2.10000, 3))
print(sol.myPow(2.00000, -2))public class Solution {
public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
return myPowUtil(x, N);
}
private double myPowUtil(double x, long n) {
if (n == 0) return 1;
double half = myPowUtil(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.myPow(2.00000, 10));
System.out.println(sol.myPow(2.10000, 3));
System.out.println(sol.myPow(2.00000, -2));
}
}#include <iostream>
class Solution {
public:
double myPow(double x, int n) {
long long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
return myPowUtil(x, N);
}
private:
double myPowUtil(double x, long long n) {
if (n == 0) return 1;
double half = myPowUtil(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}
};
int main() {
Solution sol;
std::cout << sol.myPow(2.00000, 10) << std::endl;
std::cout << sol.myPow(2.10000, 3) << std::endl;
std::cout << sol.myPow(2.00000, -2) << std::endl;
return 0;
}function myPow(x, n) {
function myPowUtil(x, n) {
if (n === 0) return 1;
const half = myPowUtil(x, Math.floor(n / 2));
if (n % 2 === 0) {
return half * half;
} else {
return half * half * x;
}
}
let N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
return myPowUtil(x, N);
}
console.log(myPow(2.00000, 10));
console.log(myPow(2.10000, 3));
console.log(myPow(2.00000, -2));#include <stdio.h>
double myPowUtil(double x, long long n) {
if (n == 0) return 1;
double half = myPowUtil(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}
double myPow(double x, int n) {
long long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
return myPowUtil(x, N);
}
int main() {
printf("%f\n", myPow(2.00000, 10));
printf("%f\n", myPow(2.10000, 3));
printf("%f\n", myPow(2.00000, -2));
return 0;
}using System;
public class Solution {
public double MyPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
return MyPowUtil(x, N);
}
private double MyPowUtil(double x, long n) {
if (n == 0) return 1;
double half = MyPowUtil(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.MyPow(2.00000, 10));
Console.WriteLine(sol.MyPow(2.10000, 3));
Console.WriteLine(sol.MyPow(2.00000, -2));
}
}In this Python solution, a nested helper function performs the recursive calculation. It divides the power by 2 recursively and uses the result to obtain xn. This structure leverages Python's concise function definitions.
Time Complexity: O(log n), Space Complexity: O(log n) due to recursion
Approach 3: Mathematics (Fast Powering)
The core idea of the fast powering algorithm is to decompose the exponent n into the sum of 1s on several binary bits, and then transform the nth power of x into the product of several powers of x.
The time complexity is O(log n), and the space complexity is O(1). Here, n is the exponent.
function myPow(x: number, n: number): number {
const qpow = (a: number, n: number): number => {
let ans = 1;
for (; n; n >>>= 1) {
if (n & 1) {
ans *= a;
}
a *= a;
}
return ans;
};
return n >= 0 ? qpow(x, n) : 1 / qpow(x, -n);
}func myPow(x float64, n int) float64 {
qpow := func(a float64, n int) float64 {
ans := 1.0
for ; n > 0; n >>= 1 {
if n&1 == 1 {
ans *= a
}
a *= a
}
return ans
}
if n >= 0 {
return qpow(x, n)
}
return 1 / qpow(x, -n)
}impl Solution {
#[allow(dead_code)]
pub fn my_pow(x: f64, n: i32) -> f64 {
let mut x = x;
let n = n as i64;
if n >= 0 {
Self::quick_pow(&mut x, n)
} else {
1.0 / Self::quick_pow(&mut x, -n)
}
}
#[allow(dead_code)]
fn quick_pow(x: &mut f64, mut n: i64) -> f64 {
// `n` should greater or equal to zero
let mut ret = 1.0;
while n != 0 {
if (n & 0x1) == 1 {
ret *= *x;
}
*x *= *x;
n >>= 1;
}
ret
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Method with Exponentiation by Squaring | Time Complexity: O(log n), Space Complexity: O(1) |
| Recursive Divide and Conquer | Time Complexity: O(log n), Space Complexity: O(log n) due to recursion |
| Mathematics (Fast Powering) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Multiplication | O(n) | O(1) | Useful for understanding the basic power computation but inefficient for large exponents |
| Iterative Exponentiation by Squaring | O(log n) | O(1) | Best general solution for interviews and production code |
| Recursive Divide and Conquer | O(log n) | O(log n) | Good when demonstrating recursion or divide-and-conquer concepts |
Frequently asked questions
Is Pow(x, n) easy or hard?
Pow(x, n) is generally classified as a medium difficulty problem. The challenge lies in recognizing the exponentiation by squaring optimization and correctly handling edge cases such as negative exponents and integer overflow.
Pow(x, n) Python/Java solution
Most solutions in Python, Java, C++, or JavaScript implement exponentiation by squaring. The algorithm keeps squaring the base and halving the exponent while multiplying the result when the exponent is odd, achieving O(log n) time complexity.
How to solve Pow(x, n) in O(log n)?
Use exponentiation by squaring. If n is even, compute (x * x)^(n/2). If n is odd, multiply one extra x and reduce the exponent. Repeatedly square the base and halve the exponent until it reaches zero, giving a logarithmic number of operations.
What is the best approach for Pow(x, n)?
Exponentiation by squaring is the most efficient approach. It reduces the exponent by half on every step, leading to O(log n) time complexity instead of O(n). The iterative version is typically preferred because it uses constant extra space while remaining easy to implement.
Is Pow(x, n) asked at Google/Amazon/Meta?
Pow(x, n) appears frequently in technical interviews at major companies including Google, Amazon, Meta, and Microsoft. It tests understanding of mathematical optimization, divide‑and‑conquer thinking, and careful handling of edge cases like negative exponents.
What data structure is used in Pow(x, n)?
The problem mainly relies on mathematical reasoning rather than complex data structures. Implementations typically use simple variables and arithmetic operations, with recursion or iterative loops to apply exponentiation by squaring.
What is the time complexity of Pow(x, n)?
The optimal exponentiation by squaring algorithm runs in O(log n) time because the exponent is divided by two in each step. A naive multiplication approach would require O(n) time since it multiplies the base repeatedly.