Is Pow(x, n) easy or hard?

Pow(x, n) is generally classified as a medium difficulty problem. The challenge lies in recognizing the exponentiation by squaring optimization and correctly handling edge cases such as negative exponents and integer overflow.

Pow(x, n) Python/Java solution

Most solutions in Python, Java, C++, or JavaScript implement exponentiation by squaring. The algorithm keeps squaring the base and halving the exponent while multiplying the result when the exponent is odd, achieving O(log n) time complexity.

How to solve Pow(x, n) in O(log n)?

Use exponentiation by squaring. If n is even, compute (x * x)^(n/2). If n is odd, multiply one extra x and reduce the exponent. Repeatedly square the base and halve the exponent until it reaches zero, giving a logarithmic number of operations.

What is the best approach for Pow(x, n)?

Exponentiation by squaring is the most efficient approach. It reduces the exponent by half on every step, leading to O(log n) time complexity instead of O(n). The iterative version is typically preferred because it uses constant extra space while remaining easy to implement.

Is Pow(x, n) asked at Google/Amazon/Meta?

Pow(x, n) appears frequently in technical interviews at major companies including Google, Amazon, Meta, and Microsoft. It tests understanding of mathematical optimization, divide‑and‑conquer thinking, and careful handling of edge cases like negative exponents.

What data structure is used in Pow(x, n)?

The problem mainly relies on mathematical reasoning rather than complex data structures. Implementations typically use simple variables and arithmetic operations, with recursion or iterative loops to apply exponentiation by squaring.

What is the time complexity of Pow(x, n)?

The optimal exponentiation by squaring algorithm runs in O(log n) time because the exponent is divided by two in each step. A naive multiplication approach would require O(n) time since it multiplies the base repeatedly.

Description Solution Video 8:10

50. Pow(x, n)

Medium39.0% acceptance22 companies

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

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² = 1/4 = 0.25

Constraints:

-100.0 < x < 100.0
-2³¹ <= n <= 2³¹-1
n is an integer.
Either x is not zero or n > 0.
-10⁴ <= xⁿ <= 10⁴

Asked at top 20 of 22 companies

Meta eBay Wix LinkedIn Qualcomm

Google Microsoft Bloomberg Amazon

TCS Adobe Walmart Labs

+8 more

Citadel ServiceNow EPAM Systems Oracle Goldman Sachs

Infosys Accenture NVIDIA

Topics

Math Recursion

8:10

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

50. Pow(x, n)

Asked at top 20 of 22 companies

Topics

Similar problems