DSA problem
Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (i.e., x^n). You may not use built-in exponentiation routines (such as Math.pow or the ** operator). The exponent n can be negative, in which case the result is 1 / x^|n|.
The naive approach multiplies x by itself |n| times in a loop, which takes O(n) time. For an exponent like n = 10^9 this is prohibitively slow. We need a way to amplify each multiplication so that the work scales with the number of bits in n rather than its magnitude.
The classic trick is exponentiation by squaring. Notice that x^n = (x^(n/2))^2 when n is even, and x^n = x * (x^(n/2))^2 when n is odd. Each recursive call halves the exponent, so the recursion depth is O(log n).
Two edge cases deserve care. First, when n is negative, we compute 1 / pow(x, -n); the only subtlety is that -Integer.MIN_VALUE overflows a 32-bit int, so Java and C++ should cast n to a 64-bit long before negation. Second, when n == 0 the answer is unconditionally 1. With those handled, the algorithm runs in O(log n) time using O(log n) recursion-stack space.
Examples
x = 2.00000, n = 101024.00000x = 2.10000, n = 39.26100x = 2.00000, n = -20.25000Constraints
- -100.0 < x < 100.0
- -2^31 <= n <= 2^31 - 1
- n is an integer.
- Either x is not zero or n > 0.
- -10^4 <= x^n <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.