50. Pow(x, n)
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.
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:
-
Initialize an accumulator (
ans
): A variableans
is initialized to 1. This will eventually hold the final result after accumulating the necessary multiplications. -
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. -
Checking if
n
is odd (using bitwise AND): Within the loop, we check if the least significant bit ofn
is 1 by usingn & 1
. This is equivalent to checking ifn
is odd. If it is, we multiply the currentans
bya
because we know we need to include this factor in our product. -
Doubling the base (
a *= a
): After dealing with the possibility ofn
being odd, we square the basea
by multiplying it by itself. This corresponds to the exponential property thata^n = (a^(n/2))^2
for evenn
. -
Halving the exponent (using bitwise shift): We then halve the exponent
n
by right-shifting it one bit usingn >>= 1
. This is equivalent to integer division by 2. Squaringa
and halvingn
is repeated untiln
becomes zero. -
Handling negative exponents: After calculating the positive power using
qpow
, if the original exponentn
was negative, we take the reciprocal of the result by returning1 / qpow(x, -n)
. This handles cases wherex
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
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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.
-
Initialize accumulator (
ans
): Setans = 1
. This will hold our final result. -
Assign base to
a
and exponent ton
: We start witha = 3
andn = 4
. -
Begin iterative process: Since
n
is not zero, enter the while loop. -
First iteration (n = 4):
- Check if
n
is odd:n & 1
is0
, meaningn
is even. Skip multiplyingans
bya
. - Square the base (
a *= a
):a
becomes9
. - Halve the exponent (
n >>= 1
):n
becomes2
.
- Check if
-
Second iteration (n = 2):
- Check if
n
is odd:n & 1
is0
, still even. Skip multiplyingans
bya
. - Square the base (
a *= a
):a
becomes81
. - Halve the exponent (
n >>= 1
):n
becomes1
.
- Check if
-
Third iteration (n = 1):
- Check if
n
is odd:n & 1
is1
, meaningn
is odd. Multiplyans
bya
:ans
becomes81
. - Square the base (
a *= a
): Althougha
becomes6561
we stop because the next step would maken
zero.
- Check if
-
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
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.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
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 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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we