Skip to main content

Pow(x, n)

LeetCode 50 | Difficulty: Medium​

Medium

Problem Description​

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

- `-100.0  0`.

- `-10^4 <= x^n <= 10^4`

Topics: Math, Recursion

Approach​

Mathematical​

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

Solutions​

Solution 1: C# (Best: 48 ms)​

MetricValue
Runtime48 ms
Memory14.5 MB
Date2019-12-15
Solution
public class Solution {
    public double MyPow(double x, int n) {
    double temp = x;
    if (n == 0)
        return 1;
    temp = MyPow(x, n / 2);
    if (n % 2 == 0)
        return temp * temp;
    else
    {
        if (n > 0)
            return x * temp * temp;
        else
            return (temp * temp) / x;
    }
    }
}

Complexity Analysis​

ApproachTimeSpace
Solution$O(n)$$O(1) to O(n)$

Interview Tips​

Key Points
  • Discuss the brute force approach first, then optimize. Explain your thought process.