Problem Statement

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

Examples

Example 1:

Input: x = 2.0000, n = 10
Output: 1024

Explanation: 2^10 = 1024

Example 2:

Input: x = 2.0000, n = -2
Output: 0.2500

Explanation: 2^(-2) = 1 / 2^2 = 1 / 4 = 0.25

Different Approaches

1️⃣ Iterative Approach (Brute Force)

Intuition:

The goal is to implement a function that computes the power of a number, x raised to n . The core idea involves repeated multiplication of x for n times. To handle both positive and negative exponents, a check for the sign of n is essential. If n is negative, the problem can be transformed by inverting x and making n positive. This approach simplifies the calculation and ensures that the function handles all possible input scenarios effectively.

Approach:

1. Initialize the result variable, ans, to 1. This serves as the base case where any number raised to the power of 0 is 1.
2. Check if the exponent, n, is less than 0.
   1. If true, invert x by setting x to 1/x and make n positive by setting n to -n. This transformation allows the handling of negative exponents.
3. Use a loop to iterate from 0 to n (converted to an integer). In each iteration, multiply ans by x. This effectively computes x raised to the power of n.
4. Return the result stored in ans, which now contains the value of x^n.

Dry Run:

Initialization:

x = 2
n = -3
ans = 1

Since n < 0 -> -3 < 0
	  x = 1 / x
	    = 1 / 2
	  n = -1 * n
	    = -1 * -3
	    = 3

First Iteration:

x = 1 / 2
n = 3
ans = 1

i = 0 < n
  = 0 < 3
  = True

ans = ans * x
    = 1 * 1 / 2
    = 1 / 2

i++

Second Iteration:

x = 1 / 2
n = 3
ans = 1 / 2

i = 1 < n
  = 1 < 3
  = True

ans = ans * x
    = 1/2 * 1/2
    = 1/4

i++

Third Iteration:

x = 1 / 2
n = 3
ans = 1 / 4

i = 2 < n
  = 2 < 3
  = True

ans = ans * x
    = 1/4 * 1/2
    = 1/8

i++

Loop Termination:

x = 1 / 2
n = 3
ans = 1 / 8

i = 3 < n
  = 3 < 3
  = False

return ans 1 / 8 which is 0.125

Code:

class Solution {
public:
    double myPow(double x, int n) {
        // Base case: any number to the power of 0 is 1
        if (n == 0) return 1; 
        // Handle negative exponents
        if (n < 0) { 
            x = 1 / x;
            n = -n;
        }
        double ans = 1;
        for (int i = 0; i < n; i++) {
            // Multiply ans by x n times
            ans *= x; 
        }
        return ans;
    }
};

int main() {
    Solution sol;
    // Output: 1024.0000
    printf("%.4f\n", sol.myPow(2.0000, 10));
    // Output: 0.2500 
    printf("%.4f\n", sol.myPow(2.0000, -2)); 
    return 0;
}

Complexity Analysis:

• Time Complexity:O(n), where n is the exponent. The loop runs n times to compute the power.
• Space Complexity:O(1), as the algorithm uses a constant amount of extra space regardless of the input size.

2️⃣ Using Recursion

To solve this problem recursively, we need to understand that calculating the power involves multiplying the base by itself for the given exponent. Recursion involves breaking down a problem into smaller instances until reaching a base case. In this case, the base case occurs when the exponent becomes zero, at which point we return 1.

Let's understand this with an example:

For instance, if the base is 2 and the exponent is 3, the power can be calculated as follows:

• Recursive call: power(2, 3)
  • Multiply the base (2) by the result of power(2, 2)
  • Recursive call: power(2, 2)
    • Multiply the base (2) by the result of power(2, 1)
    • Recursive call: power(2, 1)
      • Multiply the base (2) by the result of power(2, 0)
      • Recursive call: power(2, 0)
        • Since the exponent is zero, return 1
      • Return 1 * 2 = 2
    • Return 2 * 2 = 4
  • Return 4 * 2 = 8
• Final result: 8

Code:

#include <iostream>

// Recursive function to calculate the power of a base to an exponent
double power(double base, int exponent) {
    // Base case: If the exponent is zero
    if (exponent == 0) {
        return 1;
    }
    
    // If the exponent is negative, compute the reciprocal of the base raised to the positive exponent
    if (exponent < 0) {
        return 1 / power(base, -exponent);
    }
    
    // Recursively call power with the exponent reduced by 1
    return base * power(base, exponent - 1);
}

int main() {
    double base;
    int exponent;

    // Prompt the user to enter the base and exponent
    std::cout << "Enter the base: ";
    std::cin >> base;
    std::cout << "Enter the exponent: ";
    std::cin >> exponent;

    // Call the recursive function to calculate the power
    double result = power(base, exponent);

    // Print the result
    std::cout << "Result: " << result << std::endl;

    return 0;
}

OR:

class Solution {
public:
    // Function to calculate x raised to the power of n (x^n)
    double myPow(double x, int n) {
        // Base case: any number raised to the power of 0 is 1
        if (n == 0) {
            return 1;
        }
        // If the exponent is positive
        if (n > 0) {
            // Multiply x with the result of myPow with reduced exponent
            return x * myPow(x, n - 1);
        } else { 
            // If the exponent is negative
            // Divide 1 by x and recursively compute myPow with incremented exponent
            return 1 / x * myPow(x, n + 1);
        }
    }
};

Complexity Analysis:

• Time Complexity
  • In each recursive call, we perform a constant amount of work (multiplying the base), which can be considered as O(1).
  • The number of recursive calls depends on the exponent, which is proportional to the value of exponent.
  • Therefore, the overall time complexity of the solution is O(exponent), where exponent is the value of the exponent.
• Space Complexity
  • The space complexity of the solution is O(exponent) as well, considering the recursive calls create a call stack with exponent frames.