Pow(x, n)

Updated on 20 June, 2025
Pow(x, n) header image

Problem Statement

The task is to develop a function pow(x, n), which calculates the value of x raised to the power of n. This operation is represented mathematically as x^n. Here, x is a double precision floating-point number and n is an integer. The goal is to compute x^n under various boundary conditions like positive, negative, or zero values of n, ensuring correct and efficient handling.

Examples

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

Approach and Intuition

The computation of x raised to the power n encapsulates more than just repeatedly multiplying x by itself n times. Several insights and optimizations can be leveraged to efficiently calculate large powers, especially considering floating-point arithmetic and the limits imposed by the constraints.

Using fast exponentiation or exponentiation by squaring:

  1. Recursive approach:
    • When n is even, x^n can be reduced to (x^(n/2))^2. This reduces the number of multiplications significantly.
    • When n is odd, x^n can be written as x * x^(n-1), thus still exploiting the even case optimization by reducing n-1 to an even number.
  2. Iterative approach (often more efficient for large n):
    • Calculate x^n by iteratively squaring a base while halving the exponent, accumulating the result when the exponent is odd.

Handling different cases of n:

  • For positive n, the repeated squaring method can be directly applied.
  • For negative n, compute x^-n (using the methods above) and then take the reciprocal to get the result. This accurately handles the transformation from a negative to a positive exponent.
  • If n = 0, irrespective of the value of x (except when x is also 0 which is an indeterminate form not allowed by the constraints), the result is 1. This is a basic property of exponents.

Efficiency and limitations:

  • The recursive and iterative methods reduce the time complexity from O(n) in a naive implementation to O(log n) by reducing the number of multiplications required.
  • Edge cases due to floating-point arithmetic need careful handling, especially when n is large or when x is very small or very large.
  • Constraints help outline the boundaries of x and n to prevent overflow and underflow, ensuring the results remain within practical limits for applications.

Examples provided illustrate typical scenarios:

  • Simple positive powers (Example 1 & 2).
  • Dealing with negative powers using reciprocals (Example 3).

Solutions

  • C++
  • Java
  • C
  • JavaScript
  • Python
cpp
class Solution {
public:
    double exp_power(double base, long long exp) {
        if (exp == 0) {
            return 1.0;
        }

        if (exp < 0) {
            exp = -exp;
            base = 1.0 / base;
        }

        double product = 1.0;
        while (exp > 0) {
            if (exp % 2 == 1) {
                product *= base;
                exp--;
            }
            base *= base;
            exp /= 2;
        }
        return product;
    }

    double myPow(double x, int n) { return exp_power(x, (long long)n); }
};

The provided C++ solution efficiently computes x raised to the power n using the function myPow. This function internally calls exp_power, a helper function that employs the method of exponentiation by squaring, which is both time-efficient and space-efficient.

  • The function exp_power accepts two parameters: base (as double) and exp (as long long), initiating a process to handle powers both positive and negative:

    • If exp is zero, it immediately returns 1.0 indicating that any number raised to the power of zero is one.
    • For negative exponents, it inverts the base (base = 1.0 / base) and turns exp to positive to simplify calculation.
    • It initializes product to 1.0 which will ultimately store the result of the exponentiation.
    • Through a while loop, if exp is odd (checked using exp % 2 == 1), it multiplies product by base and decreases exp by 1 to make exp even. Then, it squares the base (for the next iteration with half of the current exp) and halves exp.
  • The main function myPow simply forwards its inputs to exp_power, effectively starting the power calculation process.

This method, by handling squared multiplications recursively and reducing the problem size with each iteration, allows for the computation of large exponents quickly and minimizes the number of multiplicative operations, thus optimizing performance.

java
class Solution {
    private double fastPower(double base, long exponent) {
        if (exponent == 0) {
            return 1.0;
        }

        if (exponent < 0) {
            exponent = -exponent;
            base = 1.0 / base;
        }

        double ans = 1.0;
        while (exponent != 0) {
            if (exponent % 2 == 1) {
                ans *= base;
                exponent--;
            }
            base *= base;
            exponent /= 2;
        }
        return ans;
    }

    public double myPow(double x, int n) {
        return fastPower(x, (long) n);
    }
}

The given Java solution efficiently computes the power of a number x raised to an integer n (x^n) using a method known as "exponentiation by squaring." This method optimizes the process by reducing the number of multiplications needed, which is crucial for large values of n. Below, find the breakdown of how the code implements this algorithm:

  • A helper function fastPower(double base, long exponent) is defined to handle the computation. The function takes into account the possibility of negative exponents by converting them to positive and taking the reciprocal of the base.

  • This function first checks if the exponent is zero, in which case it immediately returns 1.0, because any number raised to the power of zero is 1.

  • If the current exponent is odd (checked using exponent % 2 == 1), the base is multiplied to the ans, and the exponent is decremented by one to make it even. This is to ensure that the squaring process can proceed.

  • Then, the base is squared, and the exponent is halved. This process repeats until the exponent becomes zero, at which point ans will contain the correct result.

  • The main myPow(double x, int n) method, which is accessible publicly, internally calls fastPower by casting n to long to avoid potential overflow issues with integer arithmetic.

By squaring the base and halving the exponent iteratively, this solution greatly reduces the number of operations compared to the naive approach of multiplying x to itself n times, especially for large n. This makes it a highly efficient solution for power calculations in Java.

c
double power(double base, long exp) {
    if (exp == 0) return 1.0;
    if (exp < 0) {
        exp = -exp;
        base = 1.0 / base;
    }
    double res = 1.0;
    while (exp > 0) {
        if (exp % 2 == 1) {
            res *= base;
            exp--;
        }
        base = base * base;
        exp = exp / 2;
    }
    return res;
}
double myPow(double base, int exp) { return power(base, (long)exp); }

This summary explains how to compute the power of a number x raised to the exponent n using a C function. Here's how the solution works:

  • Define a helper function power(double base, long exp) to compute the result:

    • Check if the exponent exp is zero, and if so, return 1.0 immediately, since any number raised to the power of zero is 1.
    • Handle negative exponents by converting exp to a positive equivalent and inverting the base (i.e., base becomes 1.0 / base).
    • Initialize a result variable res to 1.0.
    • Use a loop to compute the power for positive exponents:
      • If the current exponent exp is odd (i.e., exp % 2 == 1), multiply res by base and decrement exp by 1.
      • Square the base and halve the exp (integer division by 2) until exp becomes zero.
    • Return the computed result res.
  • Implement the main function myPow(double base, int exp) that converts the exponent exp to a long data type and calls the helper function power(base, (long)exp) to get the final result.

This method of repeatedly squaring the base and halving the exponent, known as "exponentiation by squaring," optimizes the computation, especially for large exponents, as it reduces the number of multiplicative operations needed.

js
function expBySquaring(base, exp) {
    if (exp === 0) {
        return 1;
    }

    if (exp < 0) {
        exp = -exp;
        base = 1.0 / base;
    }

    let accumulator = 1;
    while (exp !== 0) {
        if (exp % 2 === 1) {
            accumulator *= base;
            exp -= 1;
        }
        base *= base;
        exp = Math.floor(exp / 2);
    }
    return accumulator;
}

var power = function (base, exp) {
    return expBySquaring(base, exp);
};

The provided JavaScript solution implements the power(base, exp) function, which calculates the power of a number by exponentiation using the method of exponentiation by squaring. This efficient algorithm handles different scenarios including negative exponents. Here's a breakdown of how the solution works:

  • Define expBySquaring(base, exp):

    • Return 1 if exp is zero—any number raised to the power of zero is 1.
    • If exp is negative, modify exp to be positive, and adjust base to 1.0 / base to account for the inversion.
    • Initialize an accumulator variable to 1 to hold the result of successive operations.
    • Use a while loop to process the exponentiation:
      • If exp is odd (exp % 2 === 1), multiply the accumulator by base, then decrement exp by 1 to make it even.
      • Square the base and halve exp using floor division (Math.floor(exp / 2)) to reduce the exponent systematically until it reaches zero.
    • Return the value of the accumulator once the loop terminates, yielding the final result of the exponentiation.
  • Define power(base, exp) to wrap around expBySquaring(base, exp) for simplicity and easier usage.

Apply this solution to efficiently compute the power of a number for both positive and negative exponents, leveraging the performance benefits of exponentiation by squaring particularly for larger exponents.

python
class Solution:
    def power(self, base: float, exp: int) -> float:
        if exp == 0:
            return 1

        if exp < 0:
            exp = -exp
            base = 1.0 / base

        result = 1
        while exp > 0:
            if exp % 2 == 1:
                result *= base
                exp -= 1
            base *= base
            exp //= 2
        return result

    def exponentiate(self, base: float, exp: int) -> float:
        return self.power(base, exp)

Implement the power function (x^n) in Python by following this approach where you calculate the power of base to the exponent exp. The solution uses a method that optimizes the calculation using an iterative version of exponentiation by squaring, which reduces the time complexity significantly.

  • Define the function power(base, exp) which handles both positive and negative exponents.
  • Return 1 immediately if exp is 0 since any number raised to the power of 0 is 1.
  • If exp is negative, convert it to a positive by making exp = -exp and invert the base to 1.0 / base.
  • Initialize result to 1. Use a loop to handle the multiplication of the base when the exponent is greater than 0.
  • If exp % 2 == 1, multiply the current result by the base and decrease exp by 1.
  • Square the base and halve the exp using integer division exp //= 2.
  • Return the computed result once exp becomes zero.

Additionally, define exponentiate(base, exp) which simply calls power(base, exp) to perform the actual computation. This division makes the code modular and easy to manage.

By using exponentiation by squaring, you ensure efficient computation even for large exponents, leveraging the halving of the exponent and squaring of the base at each step of the iterative process. This approach significantly reduces the number of multiplications needed compared to the straightforward approach of multiplying the base exp times.

Comments

No comments yet.