# Pow(x, n)
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/powx-n)
Canonical: https://scaleengineer.com/dsa/problems/pow(x-n)
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Infosys](https://scaleengineer.com/companies/infosys), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [ServiceNow](https://scaleengineer.com/companies/servicenow), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [eBay](https://scaleengineer.com/companies/ebay), [tcs](https://scaleengineer.com/companies/tcs), [Salesforce](https://scaleengineer.com/companies/salesforce), [Citadel](https://scaleengineer.com/companies/citadel), [Millennium](https://scaleengineer.com/companies/millennium), [Arcesium](https://scaleengineer.com/companies/arcesium)
---
## Problem
Implement [pow(x, n)](http://www.cplusplus.com/reference/valarray/pow/), 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-1`
* `n` is an integer.
* Either `x` is not zero or `n > 0`.
* `-104 <= xn <= 104`

# Approaches
## Brute Force using Simple Loop
This approach simulates the basic definition of exponentiation by repeatedly multiplying the base `x` for `n` times. It's the most straightforward but least efficient method.
**Time:** O(n) · **Space:** O(1)
**Pros:** Very simple to understand and implement.; Works correctly for small values of `n`.
**Cons:** Extremely inefficient for large values of `n`.; Will result in a 'Time Limit Exceeded' (TLE) error on most online judges due to the O(n) complexity.
### Explanation
The algorithm handles three main cases for the exponent `n`:

1.  **Positive `n`**: We initialize a result to `1.0` and multiply it by `x` exactly `n` times in a loop.
2.  **`n` is zero**: By definition, `x^0` is `1`, so we return `1.0`.
3.  **Negative `n`**: We use the property `x^-n = 1 / x^n`. To avoid integer overflow when `n` is `Integer.MIN_VALUE`, we first convert `n` to a `long`. Then, we can safely negate it. We calculate the power for the positive exponent `-n` and then take its reciprocal. A small optimization for the negative case is to compute `(1/x)^-n` instead.

```java
public class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        double ans = 1.0;
        for (long i = 0; i < N; i++) {
            ans = ans * x;
        }
        return ans;
    }
}
```
### Algorithm
- Convert the integer `n` to a long `N` to handle the `Integer.MIN_VALUE` case.
- If `N` is negative, update `x` to `1/x` and `N` to `-N`.
- Initialize a variable `ans` to `1.0`.
- Iterate from `0` to `N-1`.
- In each iteration, multiply `ans` by `x`.
- After the loop, return `ans`.

## Fast Power using Recursion (Exponentiation by Squaring)
A more efficient approach is to use the 'Exponentiation by Squaring' method, also known as binary exponentiation. This method leverages the property that `x^n = (x^2)^(n/2)` if `n` is even, and `x^n = x * (x^2)^((n-1)/2)` if `n` is odd. This significantly reduces the number of multiplications.
**Time:** O(log n) · **Space:** O(log n)
**Pros:** Significantly faster than the brute-force approach with logarithmic time complexity.; Elegant and concise recursive solution.
**Cons:** The recursion depth can be up to `log n`, which consumes stack space.; For very large `n`, this could potentially lead to a stack overflow error, although it's unlikely with the given constraints.
### Explanation
This approach is implemented recursively. We define a helper function that calculates the power.

The base case for the recursion is when the exponent `n` becomes `0`, in which case we return `1.0`.

In the recursive step, we first calculate the result for `n/2`, let's call it `half`. Then, we square `half` to get `half * half`. If `n` is even, this is our result. If `n` is odd, we need to multiply by an extra `x`.

The main `myPow` function handles the sign of `n`. If `n` is negative, we calculate `1.0 / fastPow(x, -n)`. Again, we must be careful with `n = Integer.MIN_VALUE`. A simple way is to calculate `1.0 / (fastPow(x, -(n+1)) * x)` to avoid overflow, or convert `n` to a `long`.

```java
public class Solution {
    private double fastPow(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        double half = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }

    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        return fastPow(x, N);
    }
}
```
### Algorithm
- Create a main function `myPow(x, n)` that handles the sign of `n`.
- Convert `n` to a long `N`. If `N` is negative, set `x = 1/x` and `N = -N`.
- Call a recursive helper function `fastPow(x, N)`.
- **Inside `fastPow(x, n)`:**
- If `n` is `0`, return `1.0` (base case).
- Recursively call `fastPow(x, n / 2)` and store the result in `half`.
- If `n` is even, return `half * half`.
- If `n` is odd, return `half * half * x`.

## Fast Power using Iteration (Exponentiation by Squaring)
This is the most optimal approach. It uses the same 'Exponentiation by Squaring' principle as the recursive method but implements it iteratively. This eliminates the overhead of recursion and reduces the space complexity to constant.
**Time:** O(log n) · **Space:** O(1)
**Pros:** Optimal time complexity of O(log n).; Optimal space complexity of O(1) as it avoids recursion.; Most efficient and robust solution for this problem.
**Cons:** The logic might be slightly less intuitive to grasp initially compared to the simple loop or the direct recursive translation.
### Explanation
The iterative approach works by considering the binary representation of the exponent `n`. We iterate while `n` is not zero. In each step, we check if the current least significant bit of `n` is 1. If it is, we multiply our current result by the current power of `x`. Then, we square the current power of `x` and right-shift `n` by one bit (equivalent to dividing by 2).

For example, to calculate `x^13`, the binary representation of 13 is `1101`. This means `x^13 = x^(8+4+1) = x^8 * x^4 * x^1`. The algorithm effectively computes these required powers of `x` (`x^1`, `x^2`, `x^4`, `x^8`, ...) and multiplies them into the result only when the corresponding bit in `n` is set.

As with other approaches, we handle negative exponents by taking the reciprocal of `x` and making the exponent positive. Using a `long` for the exponent is crucial to avoid overflow with `Integer.MIN_VALUE`.

```java
public class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        double ans = 1.0;
        double current_product = x;

        for (long i = N; i > 0; i /= 2) {
            if ((i % 2) == 1) {
                ans = ans * current_product;
            }
            current_product = current_product * current_product;
        }
        return ans;
    }
}
```
### Algorithm
- Convert `n` to a long `N` to handle `Integer.MIN_VALUE`.
- If `N` is negative, update `x` to `1/x` and `N` to `-N`.
- Initialize `ans` to `1.0` and `current_product` to `x`.
- Loop as long as `N > 0`.
- Inside the loop, check if `N` is odd (`N % 2 == 1`). If it is, multiply `ans` by `current_product`.
- Square `current_product` (`current_product = current_product * current_product`).
- Halve `N` by integer division (`N = N / 2`).
- After the loop finishes, return `ans`.

# Solutions
### CSharp

```csharp
public class Solution {
    public double MyPow(double x, int n) {
        return n >= 0 ? qpow(x, n) : 1.0 / qpow(x, -(long) n);
    }
    private double qpow(double a, long n) {
        double ans = 1;
        for (; n > 0; n >>= 1) {
            if ((n & 1) == 1) {
                ans *= a;
            }
            a *= a;
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  double myPow(double x, int n) {
    return n >= 0 ? qpow(x, n) : 1 / qpow(x, -(long)n);
  }
private
  double qpow(double a, long n) {
    double ans = 1;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ans = ans * a;
      }
      a = a * a;
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number} x * @param {number} n * @return {number} */ var myPow =
  function (x, n) {
    const qpow = (a, n) => {
      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);
  };

```

### CPP

```cpp
class Solution {
public:
  double myPow(double x, int n) {
    auto qpow = [](double a, long long n) {
      double ans = 1;
      for (; n; n >>= 1) {
        if (n & 1) {
          ans *= a;
        }
        a *= a;
      }
      return ans;
    };
    return n >= 0 ? qpow(x, n) : 1 / qpow(x, -(long long)n);
  }
};

```

### Python

```python
class Solution : def myPow ( self , x : float , n : int ) -> float : def qpow ( a : float , n : int ) -> float : ans = 1 while n : if n & 1 : ans *= a a *= a n >>= 1 return ans return qpow ( x , n ) if n >= 0 else 1 / qpow ( x , - n )
```