Grokking the Art of Recursion for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Pow(x,n)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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 nth power.

Example

Sr#xnOutputDescription
125322 raised to the power of 5 equals 32.
234813 raised to the power of 4 equals 81.
3501Any 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 nth power recursively, we can follow these steps:

  1. If n is equal to 0, return 1 since any number raised to the power of 0 equals 1.
  2. If n is less than 0, return 1 divided by the result of calculating x raised to the power of -n.
  3. If n is greater than 0, recursively calculate x raised to the power of n/2. Store the result in a variable temp.
  4. If n is even, return the square of temp (i.e., temp * temp).
  5. If n is odd, return x multiplied by the square of temp (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.

Image

Code

Here is the code for this algorithm:

Python3
Python3

. . . .

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.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible