How do you solve Pow(x, n) on LeetCode?

Pow(x, n) (LeetCode #50) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log n) time complexity and O(log n) space complexity. Key insight: Exponentiation by squaring is a powerful technique for reducing the number of multiplications.

What is the brute force solution for Pow(x, n)?

The brute force approach for Pow(x, n) is Brute Force, with O(n) time complexity and O(1) space complexity. The brute force approach calculates the power by multiplying the base 'x' with itself 'n' times. This is straightforward but inefficient for large values of 'n'. The optimal Optimal Solution approach improves this to O(log n).

What algorithm or data structure is used to solve Pow(x, n)?

Pow(x, n) uses the following concepts: Math, Recursion. The recommended patterns to study are: Recursion, Exponentiation by Squaring.

What are the interview tips for Pow(x, n)?

Explain your thought process clearly; don't just jump to coding. Consider edge cases like n = 0 or negative n before coding. Discuss the time and space complexity of your approach.

What are common mistakes when solving Pow(x, n)?

Forgetting to handle negative exponents correctly. Not recognizing when to use recursion effectively.

#50

Pow(x, n)

Medium

MathRecursionRecursionExponentiation by Squaring

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n)	O(log n)
Space	O(1)	O(log n)

💡

Intuition

Time O(log n)Space O(log n)

The optimal approach uses the method of exponentiation by squaring, which reduces the number of multiplications needed. This is efficient for large 'n' and works by breaking down the problem recursively.

⚙️

Algorithm

4 steps

1Step 1: If n is 0, return 1 (base case).
2Step 2: If n is negative, convert x to 1/x and n to -n.
3Step 3: If n is even, recursively calculate myPow(x * x, n / 2).
4Step 4: If n is odd, return x * myPow(x, n - 1).

solution.py10 lines

1def myPow(x, n):
2    if n == 0:
3        return 1
4    if n < 0:
5        x = 1 / x
6        n = -n
7    if n % 2 == 0:
8        return myPow(x * x, n // 2)
9    else:
10        return x * myPow(x, n - 1)

ℹ

Complexity note: The time complexity is O(log n) due to the halving of 'n' in each recursive call. The space complexity is O(log n) due to the call stack in recursion.

1Exponentiation by squaring is a powerful technique for reducing the number of multiplications.
2Handling negative exponents by inverting the base is crucial.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.