50. Pow(x, n)

MediumRecursionMath
Leetcode Link

Problem Description

The task here is to implement a function that calculates the result of raising a number x to the power of n. In mathematical terms, you're asked to compute x^n. This function should work with x as a float (meaning it can be a decimal number) and n as an integer (which can be positive, negative, or zero).

Intuition

The intuitive approach to solve exponentiation could be to multiply x by itself n times. However, this method is not efficient for large values of n as it would have linear complexity O(n). Instead, we can use the "fast power algorithm," or "binary exponentiation," which reduces the time complexity substantially to O(log n).

This optimized solution is based on the principle that for any number a and integer n, the power a^n can be broken down into smaller powers using the properties of exponents. Specifically, if n is even, a^n can be expressed as (a^(n/2))^2, and if n is odd, it can be written as a*(a^((n-1)/2))^2. Applying these properties repeatedly allows us to reduce the problem into smaller subproblems, efficiently using divide-and-conquer strategy.

In this code, the function qpow implements this efficient algorithm using a loop, squaring a and halving n at each iteration, and multiplying to the answer when n is odd (detected by n & 1 which checks the least significant bit). The loop continues until n becomes 0, which is when we have multiplied enough factors into ans to give us our final result.

If the exponent n is negative, we calculate x^(-n) and then take its reciprocal, as by mathematical rule, x^(-n) equals 1/(x^n). This is why, in the final return statement, the solution checks if n is non-negative and either returns qpow(x, n) or 1 / qpow(x, -n) accordingly.

Learn more about Recursion and Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Solution Approach

The solution uses a helper function called qpow to implement a fast exponentiation algorithm iteratively. The function takes two parameters, a which represents the base number x, and n which represents the exponent. Here's a walkthrough of how the algorithm works:

  1. Initialize an accumulator (ans): A variable ans is initialized to 1. This will eventually hold the final result after accumulating the necessary multiplications.

  2. Iterative process: A while loop is set up to run as long as n is not zero. Each iteration of this loop represents a step in the exponentiation process.

  3. Checking if n is odd (using bitwise AND): Within the loop, we check if the least significant bit of n is 1 by using n & 1. This is equivalent to checking if n is odd. If it is, we multiply the current ans by a because we know we need to include this factor in our product.

  4. Doubling the base (a *= a): After dealing with the possibility of n being odd, we square the base a by multiplying it by itself. This corresponds to the exponential property that a^n = (a^(n/2))^2 for even n.

  5. Halving the exponent (using bitwise shift): We then halve the exponent n by right-shifting it one bit using n >>= 1. This is equivalent to integer division by 2. Squaring a and halving n is repeated until n becomes zero.

  6. Handling negative exponents: After calculating the positive power using qpow, if the original exponent n was negative, we take the reciprocal of the result by returning 1 / qpow(x, -n). This handles cases where x should be raised to a negative power.

Data Structures: The solution does not use any complicated data structures; it relies on simple variables to hold intermediate results (ans, a).

Patterns: The iterative process exploits the divide-and-conquer paradigm, breaking the problem down into smaller subproblems of squaring the base and halving the exponent.

Algorithm Efficiency: Because of the binary exponentiation technique, the time complexity of the algorithm is O(log n), which is very efficient even for very large values of n.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following uses divide and conquer strategy?

Example Walkthrough

Let's walk through the iterative fast exponentiation technique using an example where we want to calculate 3^4, which is 3 raised to the power of 4.

  1. Initialize accumulator (ans): Set ans = 1. This will hold our final result.

  2. Assign base to a and exponent to n: We start with a = 3 and n = 4.

  3. Begin iterative process: Since n is not zero, enter the while loop.

  4. First iteration (n = 4):

    • Check if n is odd: n & 1 is 0, meaning n is even. Skip multiplying ans by a.
    • Square the base (a *= a): a becomes 9.
    • Halve the exponent (n >>= 1): n becomes 2.

  5. Second iteration (n = 2):

    • Check if n is odd: n & 1 is 0, still even. Skip multiplying ans by a.
    • Square the base (a *= a): a becomes 81.
    • Halve the exponent (n >>= 1): n becomes 1.

  6. Third iteration (n = 1):

    • Check if n is odd: n & 1 is 1, meaning n is odd. Multiply ans by a: ans becomes 81.
    • Square the base (a *= a): Although a becomes 6561 we stop because the next step would make n zero.

  7. Exponent 0 check: The while loop exits because n is now zero.

Since we never had a negative power, we don't need to consider taking the reciprocal of ans, and the final answer for 3^4 is in ans, which is 81.

In this example, you can see we only had to iterate 3 times to compute 3^4, which is more efficient than multiplying 3 by itself 4 times. The optimized algorithm has a significant advantage as the values of n increase in magnitude.

Solution Implementation

1class Solution:
2    def myPow(self, x: float, n: int) -> float:
3        # Inner function to perform the quick exponentiation.
4        # This reduces the number of multiplications needed.
5        def quick_power(base: float, exponent: int) -> float:
6            result = 1.0
7            # Continue multiplying the base until the exponent is zero
8            while exponent:
9                # If exponent is odd, multiply the result by the base
10                if exponent & 1:
11                    result *= base
12                # Square the base (equivalent to base = pow(base, 2))
13                base *= base
14                # Right shift exponent by 1 (equivalent to dividing by 2)
15                exponent >>= 1
16            return result
17
18        # If n is non-negative, call quick_power with x and n directly.
19        # Otherwise, calculate the reciprocal of the positive power.
20        return quick_power(x, n) if n >= 0 else 1 / quick_power(x, -n)
21
1class Solution {
2    public double myPow(double x, int n) {
3        // If power n is non-negative, calculate power using helper method
4        if (n >= 0) {
5            return quickPow(x, n);
6        } else {
7            // If power n is negative, calculate the inverse of the power
8            return 1 / quickPow(x, -(long) n);
9        }
10    }
11
12    private double quickPow(double base, long exponent) {
13        double result = 1; // Initialize result to neutral element for multiplication
14
15        // Loop through all bits of the exponent
16        while (exponent > 0) {
17            // If the current bit is set, multiply the result by the base
18            if ((exponent & 1) == 1) {
19                result *= base;
20            }
21            // Square the base for the next bit in the exponent
22            base *= base;
23            // Shift exponent to the right to process the next bit
24            exponent >>= 1;
25        }
26      
27        // Return the final result of base raised to the exponent
28        return result;
29    }
30}
31
1class Solution {
2public:
3    // Function to perform exponentiation
4    double myPow(double x, int n) {
5        // Inner function to calculate power using Quick Power Algorithm (also known as Binary Exponentiation)
6        auto quickPow = [](double base, long long exponent) -> double {
7            double result = 1.0; // Initialize the result to 1, as anything to the power of 0 is 1
8            while (exponent > 0) { // Iterate until the exponent becomes 0
9                if (exponent & 1) { // If the exponent is odd, multiply the current result by the base
10                    result *= base;
11                }
12                base *= base; // Square the base
13                exponent >>= 1; // Right shift exponent by 1 (divide the exponent by 2)
14            }
15            return result; // Return the final result of base raised to the exponent
16        };
17
18        // Check the sign of the exponent and call quickPow function
19        // If 'n' is negative, we take the reciprocal of base raised to the power of absolute value of 'n'
20        // We cast 'n' to long long to handle cases when n is INT_MIN, which flips to positive out of range if n is an int
21        return n >= 0 ? quickPow(x, n) : 1.0 / quickPow(x, -(long long) n);
22    }
23};
24
1function myPow(x: number, n: number): number {
2    // A helper function to calculate the power using quick exponentiation
3    const quickPow = (base: number, exponent: number): number => {
4        let result = 1; // Initialize result to 1
5
6        // Loop until the exponent becomes zero
7        while (exponent) {
8            // If exponent is odd, multiply the result by the current base
9            if (exponent & 1) {
10                result *= base;
11            }
12            base *= base; // Square the base
13            exponent >>>= 1; // Right shift exponent by 1 bit to divide it by 2
14        }
15        return result; // Return the calculated power
16    };
17
18    // If the exponent n is non-negative, just use quickPow() directly
19    // If the exponent n is negative, take the reciprocal of the positive power
20    return n >= 0 ? quickPow(x, n) : 1 / quickPow(x, -n);
21}
22
Not Sure What to Study? Take the 2-min Quiz：

How many ways can you arrange the three letters A, B and C?

Time and Space Complexity

The given code implements the binary exponentiation algorithm to calculate x raised to the power n.

Time Complexity

The time complexity of the algorithm is O(log n). This is because the while loop runs for the number of bits in the binary representation of n. In each iteration, n is halved by the right shift operation (n >>= 1), which reduces the number of iterations to the logarithm of n, hence O(log n).

Space Complexity

The space complexity of the algorithm is O(1). The function qpow only uses a constant amount of additional space for variables ans and a, which are used to keep track of the cumulative product and the base that's being squared in each iteration. There is no use of any data structure that grows with the input size, so the space requirement remains constant irrespective of n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫