Skip to main content

Math Basics

Implement Power Function (pow(x,n)) Solution in C++/Java/Python/JS

Implement Power function (pow(x,n)) question description
implement-power-function-pow-x-n-problem-description

Description

Implement pow(x,n), which calculates x raised to the power n (i.e., xn).

Examples

Input: x = 2.00000, n = 10
Output: 1024.00000

Input: x = 2.10000, n = 3
Output: 9.26100

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Constriants

  • -100.0 < x < 100.0
  • -231 <= n <= 231-1
  • n is an integer.
  • Either x is not zero or n > 0.
  • -104 <= xn <= 104
💡
Try Solving "Pow(x,n)" Yourself First !!
Implementing the power function involves different approaches to get to a working algorithm. We will derive observations taking examples and finalise the most optimal one. Let's now visit all the approaches possible and conclude the most efficient of all !!

Understanding the Problem

We need to calculate xn, meaning multiplying xxx by itself n times. Mathematically:

xn = x * x * x * ...* x (n times)

This problem might seem simple, but different constraints (such as large values of n, negative n, or fractional x) require us to think carefully about our approach.

Naive Approach

Let's start with the simplest way, which directly follows the mathematical definition that says if we want to calculate xn , we will multiply x, n times.

The approach involves

  • Start with a variable result = 1.
  • Multiply result by x, n times.
  • If n<0, we compute x-n as 1/xn

Implement Power function (pow(x,n)) Solution (Naive Approach)

Let's see the pow(x,y) code in C++, Java, Python and JavaScript.

"Implement Power function (pow(x,n))" Code in all Languages.
1. Implement Power function (pow(x,n)) solution in C++ Try on Compiler 
// Function to compute x^n using Naïve Iterative Method
double powNaive(double x, int n) {

    // Initialize result to 1.0
    double result = 1.0;

    // Compute absolute value of exponent to handle negative cases
    int power = abs(n);

    // Multiply x by itself power times
    for (int i = 0; i < power; i++) {
        result *= x;
    }

    // If exponent was negative, return reciprocal of result
    return (n < 0) ? (1 / result) : result;
}

2. Implement Power function (pow(x,n)) Solution in Java Try on Compiler 
public class PowerNaive {

    // Function to compute x^n using Naïve Iterative Method
    static double powNaive(double x, int n) {

        // Initialize result to 1.0
        double result = 1.0;

        // Compute absolute value of exponent to handle negative cases
        int power = Math.abs(n);

        // Multiply x by itself power times
        for (int i = 0; i < power; i++) {
            result *= x;
        }

        // If exponent was negative, return reciprocal of result
        return (n < 0) ? (1 / result) : result;
    }
}

3. Implement Power function (pow(x,n)) Solution in Python Try on Compiler 
# Function to compute x^n using Naïve Iterative Method
def pow_naive(x, n):

    # Initialize result to 1.0
    result = 1.0

    # Compute absolute value of exponent to handle negative cases
    power = abs(n)

    # Multiply x by itself power times
    for _ in range(power):
        result *= x

    # If exponent was negative, return reciprocal of result
    return (1 / result) if n < 0 else result

4. Implement Power function (pow(x,n)) solution in JavaScript Try on Compiler 
// Function to compute x^n using Naïve Iterative Method
function powNaive(x, n) {

    // Initialize result to 1.0
    let result = 1.0;

    // Compute absolute value of exponent to handle negative cases
    let power = Math.abs(n);

    // Multiply x by itself power times
    for (let i = 0; i < power; i++) {
        result *= x;
    }

    // If exponent was negative, return reciprocal of result
    return (n < 0) ? (1 / result) : result;
}

Implement Power function (pow(x,n)) Complexity Analysis

Time Complexity: O(n)

We multiply x n number of times, hence the loop iterates for n times.
The total time complexity is O(n)

Space Complexity: O(1)

Since we use few variables, the space complexity is O(1).

If we observe the constraints for the given description, it's "-100.0 < x < 100.0" & "-231 <= n <= 231-1". We have to be a bit faster with the approach. Is there any other way to find the pow(x,n). Let's find it out !!

Optimal Approach

Intuition

We need to reduce the number of multiplications. What if we use the properties of exponents to optimize?
To speed up the computation, we need to break down x^n in a way that reduces the number of multiplications.

The key idea:
Instead of multiplying x repeatedly, we use the properties of exponents:

Why Does This Work?

Case 1: When n is Even
If n is even, say n=10, we can break it down:

Here, we compute x^5 (which itself follows the power rule), and then square it. This reduces the number of multiplications.

Case 2: When n is Odd

If n is odd, say n=9, we split it as:

Here, we separate one multiplication of x and reduce the problem to computing x^4, which is an even power.

So, the steps to calculate 2^10 is

This reduces our problem size by half in each step! So, instead of O(n) complexity, we now have O(log n). Huge improvement!

 Now, this approach can be solved using two approaches

  1. Recursive
  2. Iterative

Let's first see the Recursive Algorithm to Implement Power function (pow(x,y))

Implement Power function (pow(x,n)) Algorithm (Recursive)

Base Case: If n == 0, return 1 (since any number raised to the power 0 is 1).

Recursive Step: Compute half = powRecursive(x, n / 2), which recursively calculates x raised to half the exponent.

Even or Odd Exponent:

  • If n is even, return half * half
  • If n is odd, return x * half * half

Now, let's see how we can code this up

Let's visualize Implement Power function (pow(x,n)) Solution

implement-power-function-pow-x-n-flow-chart

Implement Power function (pow(x,n)) Solution (Recursive Approach)

Let's see the recursive pow(x,n) code in C++, Java, Python and JavaScript.

"Implement Recursive Power function (pow(x,n))" Code in all Languages.
1. Implement Power function (pow(x,n)) solution in C++ Try on Compiler 
// Recursive function to calculate x^n
double powRecursive(double x, int n) {

    // Base case: Any number to the power of 0 is 1
    if (n == 0) return 1;

    // Recursively compute x^(n/2)
    double half = powRecursive(x, n / 2);

    // If n is even, return (x^(n/2))^2
    if (n % 2 == 0) return half * half;

    // If n is odd, return x * (x^(n/2))^2
    return x * half * half;
}

2. Implement Power function (pow(x,n)) Solution in Java Try on Compiler 
public class PowerFunction {

    // Recursive function to calculate x^n
    static double powRecursive(double x, int n) {

        // Base case: Any number to the power of 0 is 1
        if (n == 0) return 1;

        // Recursively compute x^(n/2)
        double half = powRecursive(x, n / 2);

        // If n is even, return (x^(n/2))^2
        if (n % 2 == 0) return half * half;

        // If n is odd, return x * (x^(n/2))^2
        return x * half * half;
    }
}

3. Implement Power function (pow(x,n)) Solution in Python Try on Compiler 
# Recursive function to calculate x^n
def pow_recursive(x, n):

    # Base case: Any number to the power of 0 is 1
    if n == 0:
        return 1

    # Recursively compute x^(n//2)
    half = pow_recursive(x, n // 2)

    # If n is even, return (x^(n//2))^2
    if n % 2 == 0:
        return half * half

    # If n is odd, return x * (x^(n//2))^2
    return x * half * half

4. Implement Power function (pow(x,n)) solution in JavaScript Try on Compiler 
// Recursive function to calculate x^n
function powRecursive(x, n) {

    // Base case: Any number to the power of 0 is 1
    if (n === 0) return 1;

    // Recursively compute x^(n/2)
    let half = powRecursive(x, Math.floor(n / 2));

    // If n is even, return (x^(n/2))^2
    if (n % 2 === 0) return half * half;

    // If n is odd, return x * (x^(n/2))^2
    return x * half * half;
}

Implement Power function (pow(x,n)) Complexity Analysis

Time Complexity: O(logn)

Recursive Call Pattern

  • The function reduces the exponent n by half in each recursive call.
  • This results in logarithmic recursion depth, forming a recursive tree.

Recurrence Relation

  • Let T(n) be the number of operations required to compute powRecursive(x, n).
  • The function makes one recursive call with n/2, and performs constant time multiplication.

Recurrence Relation

  • Let T(n) be the number of operations required to compute powRecursive(x, n).
  • The function makes one recursive call with n/2, and performs constant time multiplication.

T(n)=T(n/2)+O(1)
Using the Master Theorem (Case 2: a=1,b=2,d=0), we solve: T(n)=O(log⁡n)

Final Time Complexity: O(log⁡n)

Space Complexity: O(logn)

Recursive Stack Depth

  • Since we make one recursive call per level, the recursion depth is O(log n).
  • Each function call stores a single variable (half), so space per function call is O(1).
  • The total space used is for the recursive call stack, which has O(log n) depth.

Final Space Complexity: O(log⁡n)
This is due to the recursive stack.

This was efficient than the naive approach we followed at first, but an extra space for the call stack!!
Let's minimize it!!
Seems logical! But let’s analyze the time complexity. If n is a large number, say 1,000,000, we are performing 1,000,000 multiplications. That’s O(n) time complexity. Can we do better?

Implement Power function (pow(x,n)) Algorithm (Iterative)

Handle Negative Exponent:

  • Convert n to a long (N = n) to handle edge cases like n = INT_MIN.
  • If N is negative:
    • Invert x (x = 1 / x).
    • Convert N to positive (N = -N).

Initialize the Result: Set result = 1.0 to store the final power value.

Iterate While N > 0:

  • If N is odd (N % 2 == 1), multiply result by x.
  • Square x (x = x * x) to move to the next power of two.
  • Halve N (N = N / 2) to process the next bit.

Return the Computed Result: The final value of result holds x^n.

Implement Power function (pow(x,n)) Solution (Iterative Approach)

Let's see the iterative pow(x,n) code in C++, Java, Python and JavaScript.

"Implement Iterative Power function (pow(x,n))" Code in all Languages.
1. Implement Power function (pow(x,n)) solution in C++ Try on Compiler 
// Function to compute x^n using Iterative Exponentiation by Squaring
double myPow(double x, int n) {

    // Convert n to long long to handle edge cases like INT_MIN
    long long temp = n;

    // If exponent is negative, invert the base and make exponent positive
    if (temp < 0) {
        x = 1 / x;
        temp = -temp;
    }

    // Initialize result variable
    double result = 1.0;

    // Loop while exponent is greater than 0
    while (temp > 0) {

        // If exponent is odd, multiply result by current base
        if (temp % 2 == 1) {
            result *= x;
        }

        // Square the base
        x *= x;

        // Halve the exponent
        temp /= 2;
    }

    // Return the computed power
    return result;
}

2. Implement Power function (pow(x,n)) Solution in Java Try on Compiler 
public class PowerFunction {

    // Function to compute x^n using Iterative Exponentiation by Squaring
    static double myPow(double x, int n) {
        
        // Convert n to long to handle edge cases like Integer.MIN_VALUE
        long temp = n;

        // If exponent is negative, invert the base and make exponent positive
        if (temp < 0) {
            x = 1 / x;
            temp = -temp;
        }

        // Initialize result variable
        double result = 1.0;

        // Loop while exponent is greater than 0
        while (temp > 0) {

            // If exponent is odd, multiply result by current base
            if (temp % 2 == 1) {
                result *= x;
            }

            // Square the base
            x *= x;

            // Halve the exponent
            temp /= 2;
        }

        // Return the computed power
        return result;
    }
}

3. Implement Power function (pow(x,n)) Solution in Python Try on Compiler 
# Function to compute x^n using Iterative Exponentiation by Squaring
def my_pow(x, n):

    # Convert n to long equivalent (Python handles large integers automatically)
    temp = n

    # If exponent is negative, invert the base and make exponent positive
    if temp < 0:
        x = 1 / x
        temp = -temp

    # Initialize result variable
    result = 1.0

    # Loop while exponent is greater than 0
    while temp > 0:

        # If exponent is odd, multiply result by current base
        if temp % 2 == 1:
            result *= x

        # Square the base
        x *= x

        # Halve the exponent
        temp //= 2

    # Return the computed power
    return result

4. Implement Power function (pow(x,n)) solution in JavaScript Try on Compiler 
// Function to compute x^n using Iterative Exponentiation by Squaring
function myPow(x, n) {

    // Convert n to a long equivalent
    let temp = BigInt(n);

    // If exponent is negative, invert the base and make exponent positive
    if (temp < 0) {
        x = 1 / x;
        temp = -temp;
    }

    // Initialize result variable
    let result = 1.0;

    // Loop while exponent is greater than 0
    while (temp > 0) {

        // If exponent is odd, multiply result by current base
        if (temp % 2n === 1n) {
            result *= x;
        }

        // Square the base
        x *= x;

        // Halve the exponent
        temp /= 2n;
    }

    // Return the computed power
    return result;
}

Implement Power function (pow(x,n)) Complexity Analysis

Time Complexity: O(logn)

Recursive Call Pattern

  • The function reduces the exponent n by half in each recursive call.
  • This results in logarithmic recursion depth, forming a recursive tree.

Recurrence Relation

  • Let T(n) be the number of operations required to compute powRecursive(x, n).
  • The function makes one recursive call with n/2, and performs constant time multiplication.

Recurrence Relation

  • Let T(n) be the number of operations required to compute powRecursive(x, n).
  • The function makes one recursive call with n/2, and performs constant time multiplication.

T(n)=T(n/2)+O(1)
Using the Master Theorem (Case 2: a=1,b=2,d=0), we solve: T(n)=O(log⁡n)

Final Time Complexity: O(log⁡n)

Space Complexity: O(1)

We use few variables which accumulates to a constant space, hence the total space complexity is O(1).

Figuring out the Iterative approach was faster with respect to time addition to which it consumed constant space.
But we as learners of LearnYard must find a more better solution which help us to run the solution faster in competitive environments.

Most Optimal Approach (Bit Manipulation)

Intuition

We noticed that we were dividing n by 2 at every step. That means n can be represented in binary. What if we process the exponent bit by bit?

Example: Computing 3^13
First, represent 13 in binary: 1101 (base 2)

How Does Bit Manipulation Work Here?
Every number can be represented in binary. The core idea is:

This means we can break down the exponentiation process using bits:

  1. If the current bit of n is set (1), we multiply the current result by x.
  2. Regardless, square x in each step and shift the bits of n to the right.

 Example: Computing 3^13

First, represent 13 in binary: (1101)2
which means

 Step-by-Step Calculation

Final result:

Here is the step-by-step calculation of 3^13 presented in a properly formatted table:

StepBinary of nOperation
Start1101Start with x = 3
10001Multiply result by 3
20010Square 3 to get 9, no multiply
30100Square 9 to get 81, no multiply
41000Square 81 to get 6561, multiply result

Final Computation:
3^13 = 3 * 81 * 6561 = 1594323

How Does Bit Manipulation Help?
Instead of using division (/) and modulus (%), we can efficiently use bitwise shifting (>>) and AND operations (&).

Bitwise Rules
Checking if n is odd: Instead of n % 2 == 1, use n & 1.
Dividing n by 2: Instead of n = n / 2, use n >>= 1.

Implement Power function (pow(x,n)) Algorithm (Bit Manipulation)

Start with result = 1.

While n>0:

  • If n is odd (n & 1 == 1), multiply result by x.
  • Square x.
  • Right shift n (n >>= 1).

Let's now look at the dry-run

Dry-Run

Dry-Run for powBitManipulation(2, 13)

Given Input:

  • x = 2
  • n = 13

Step 1: Initialization

  • N = 13 (unchanged since n is positive)
  • result = 1.0

Step 2: Loop Execution

  1. Iteration 1N = 1101 (binary) = 13 (decimal), LSB is 1 (odd)
    • Multiply result by x → result = 1.0 * 2 = 2
    • Square x → x = 2 * 2 = 4
    • Right shift N → N = 6
  3. Iteration 2
    • N = 0110 (binary) = 6 (decimal), LSB is 0 (even)
    • result remains 2
    • Square x → x = 4 * 4 = 16
    • Right shift N → N = 3
  5. Iteration 3
    • N = 0011 (binary) = 3 (decimal), LSB is 1 (odd)
    • Multiply result by x → result = 2 * 16 = 32
    • Square x → x = 16 * 16 = 256
    • Right shift N → N = 1
  7. Iteration 4
    • N = 0001 (binary) = 1 (decimal), LSB is 1 (odd)
    • Multiply result by x → result = 32 * 256 = 8192
    • Right shift N → N = 0 (loop ends)

Final Output:

  • result = 8192
  • Thus, 2^13 = 8192 is correctly computed.

Let's visualize the Implement Power function (pow(x,n)) Solution dry-run with a video !!

0:00
/1:13

implement-power-function-pow-x-n-optimal-approach-animation

Implement Power function (pow(x,n)) Solution (Bit Manipulation Approach)

 Let's see the bit manipulation pow(x,n) code in C++, Java, Python and JavaScript.

"Implement Bit Manipulation Power function (pow(x,n))" Code in all Languages.
1. Implement Power function (pow(x,n)) solution in C++ Try on Compiler 
// Function to compute x^n using Bit Manipulation Exponentiation
double powBitManipulation(double x, int n) {

    // Convert n to long long to handle edge cases like INT_MIN
    long long temp = n;

    // If exponent is negative, invert the base and make exponent positive
    if (temp < 0) {
        x = 1 / x;
        temp = -temp;
    }

    // Initialize result variable
    double result = 1.0;

    // Loop while exponent is greater than 0
    while (temp > 0) {

        // If the lowest bit of N is 1, multiply result by current base
        if (temp & 1) {
            result *= x;
        }

        // Square the base
        x *= x;

        // Right shift the exponent (equivalent to dividing by 2)
        temp >>= 1;
    }

    // Return the computed power
    return result;
}

2. Implement Power function (pow(x,n)) Solution in Java Try on Compiler 
public class PowerBitManipulation {

    // Function to compute x^n using Bit Manipulation Exponentiation
    static double powBitManipulation(double x, int n) {

        // Convert n to long to handle edge cases like Integer.MIN_VALUE
        long temp = n;

        // If exponent is negative, invert the base and make exponent positive
        if (temp < 0) {
            x = 1 / x;
            temp = -temp;
        }

        // Initialize result variable
        double result = 1.0;

        // Loop while exponent is greater than 0
        while (temp > 0) {

            // If the lowest bit of N is 1, multiply result by current base
            if ((temp & 1) == 1) {
                result *= x;
            }

            // Square the base
            x *= x;

            // Right shift the exponent (equivalent to dividing by 2)
            temp >>= 1;
        }

        // Return the computed power
        return result;
    }
}

3. Implement Power function (pow(x,n)) Solution in Python Try on Compiler 
# Function to compute x^n using Bit Manipulation Exponentiation
def pow_bit_manipulation(x, n):

    # Convert n to long equivalent (Python handles large integers automatically)
    temp = n

    # If exponent is negative, invert the base and make exponent positive
    if temp < 0:
        x = 1 / x
        temp = -temp

    # Initialize result variable
    result = 1.0

    # Loop while exponent is greater than 0
    while temp > 0:

        # If the lowest bit of N is 1, multiply result by current base
        if temp & 1:
            result *= x

        # Square the base
        x *= x

        # Right shift the exponent (equivalent to dividing by 2)
        temp >>= 1

    # Return the computed power
    return result

4. Implement Power function (pow(x,n)) solution in JavaScript Try on Compiler 
// Function to compute x^n using Bit Manipulation Exponentiation
function powBitManipulation(x, n) {

    // Convert n to a long equivalent
    let temp = BigInt(n);

    // If exponent is negative, invert the base and make exponent positive
    if (N < 0) {
        x = 1 / x;
        N = -N;
    }

    // Initialize result variable
    let result = 1.0;

    // Loop while exponent is greater than 0
    while (temp > 0n) {

        // If the lowest bit of N is 1, multiply result by current base
        if (temp & 1n) {
            result *= x;
        }

        // Square the base
        x *= x;

        // Right shift the exponent (equivalent to dividing by 2)
        temp >>= 1n;
    }

    // Return the computed power
    return result;
}

Implement Power function (pow(x,n)) Complexity Analysis

Time Complexity: O(logn)

Recursive Call Pattern

  • The function reduces the exponent n by half in each recursive call.
  • This results in logarithmic recursion depth, forming a recursive tree.

Recurrence Relation

  • Let T(n) be the number of operations required to compute powRecursive(x, n).
  • The function makes one recursive call with n/2, and performs constant time multiplication.

Recurrence Relation

  • Let T(n) be the number of operations required to compute powRecursive(x, n).
  • The function makes one recursive call with n/2, and performs constant time multiplication.

T(n)=T(n/2)+O(1)
Using the Master Theorem (Case 2: a=1,b=2,d=0), we solve: T(n)=O(log⁡n)

Final Time Complexity: O(log⁡n)

Space Complexity: O(1)

We use few variables which accumulates to a constant space, hence the total space complexity is O(1).

Learning Tip

We explored multiple approaches:

  1. Naive approach (O(n)) → Simple but slow.
  2. Recursive approach (O(log n)) → Faster but uses extra space.
  3. Iterative approach (O(log n)) → Space-efficient.
  4. Bit Manipulation approach (O(log n)) → Fastest!

Using bitwise operations speeds up exponentiation even further. This method is widely used in competitive programming and high-performance computing.

So, if someone asks how to compute x^n efficiently, we now know that binary exponentiation is the best approach!

Real World Example

Bitwise operations make exponentiation even faster—this is used in cryptography, modular arithmetic, and computer graphics!

Similar Problems

Power of Two

Given an integer n, return true if it is a power of two. Otherwise, return false.
An integer n is a power of two, if there exists an integer x such that n == 2x.

Power of Three

Given an integer n, return true if it is a power of three. Otherwise, return false.
An integer n is a power of three, if there exists an integer x such that n == 3x.