0% completed
Problem Statement
Write a Recursive Approach to Calculate Power of Integer to N Pow(x,n).
Given an integer x
and an integer n
, write a recursive function to calculate the power of x
to the n
th power.
Example
Sr# | x | n | Output | Description |
---|---|---|---|---|
1 | 2 | 5 | 32 | 2 raised to the power of 5 equals 32. |
2 | 3 | 4 | 81 | 3 raised to the power of 4 equals 81. |
3 | 5 | 0 | 1 | Any number raised to the power of 0 equals 1 (x^0 = 1). |
Constraints:
-100.0 < x < 100.0
- -2<sup>31</sup> <= n <= 2<sup>31</sup>-1
n
is an integer.- Either
x
is not zero or n > 0. - -10<sup>4</sup> <= x<sup>n</sup> <= 10<sup>4</sup>
Solution
To calculate the power of x
to the n
th power recursively, we can follow these steps:
- If
n
is equal to 0, return 1 since any number raised to the power of 0 equals 1. - If
n
is less than 0, return 1 divided by the result of calculatingx
raised to the power of-n
. - If
n
is greater than 0, recursively calculatex
raised to the power ofn/2
. Store the result in a variabletemp
. - If
n
is even, return the square oftemp
(i.e.,temp * temp
). - If
n
is odd, returnx
multiplied by the square oftemp
(i.e.,x * temp * temp
).
This approach works by dividing the power n
into smaller subproblems, reducing the number of recursive calls. By utilizing the property that x^(2k)
is equal to (x^k)^2
, we can optimize the computation and reduce the time complexity.
Code
Here is the code for this algorithm:
Time and Space Complexity
The time complexity of this algorithm is O(log N) because we divide the problem size in half with each recursive call. The space complexity is O(log N) as well because the maximum depth of the recursion is log n.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible