Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (i.e., x^n). Use the fast exponentiation algorithm to achieve O(log n) time complexity.

30:00

Pow(x, n)
medium
Topics
Companies

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n). Use the fast exponentiation algorithm to achieve O(log n) time complexity.

Example 1:
Input: {"x":2,"n":10}
Output: 1024.0
Constraints:

  • −100.0<x<100.0-100.0 < x < 100.0

  • −231≤n≤231−1-2^{31} \leq n \leq 2^{31} - 1

  • nn is an integer.

  • Either x≠0x \neq 0 or n>0n > 0.

  • −104≤xn≤104-10^4 \leq x^n \leq 10^4

Input
arr ={"x":2,"n":10}

Calculate 2^10 using fast exponentiation

210

Current x

2

Current n

10

Result

1

Fast Exponentiation (Binary):

x^n = (x²)^(n/2) if n is even

x^n = x × (x²)^((n-1)/2) if n is odd

Time: O(log n) instead of O(n)

Multiply (n odd)
Square x
Variables
No variables to display
DepthFunction Call
Stack empty
0/6