Striver's SDE Sheet Journey - #14 Pow(x,n)

Problem Statement :-

Given a double x and integer n, calculate x raised to power n. Basically Implement pow(x, n).

Example

Input : x = 2.00000, n = 10

Result : 1024.00000

Solution 1

The simple approach to find pow(x,n) is to initialize a variable ans and run a loop from 1 to n, keep multiplying x with ans.

step-1 Initialise a variable ans = 1.0.

step-2 run a loop from 1 to n.

1. ans = ans * x

step-3 if exponent n < 0 then return 1 / ans.

step-4 return ans.

Java

class Solution {
    public double myPow(double x, int n) {
        double ans = 1.0;

         for(int i=0; i<Math.abs(n); i++){
               ans = ans * x;
            }
        if(n < 0){
           ans = 1 / ans; 
        }

        return ans;
    }
}

Time Complexity : O(n)
Space Complexity : O(1)

Solution 2

this problem can be solved by the Divide & Conquer technique.
so what we are going to do in this approach, we recursively reduce the exponent N by half and compute them individually.

let's understand this approach with an example.

x = 2, n = 12

in this example, we need to find 2^12

reduce exponent N by half.

1. 2^12 ----> 2^6 * 2^6

2. 2^6 -----> 2^3 * 2^3

3. 2^3 -----> 2 * 2^1 * 2^1

4. 2^1 -----> 2 * 2^0 * 2^0

5. 2^0 -----> 1

now, we know that 2^0 is 1 then,

4. 2^1 -----> 2 * 2^0 * 2^0
2^1 -----> 2 * 1 * 1

3. 2^3 -----> 2 * 2^1 * 2^1
2^3 -----> 2 * 2 * 2
2^3 -----> 8

2. 2^6 -----> 2^3 * 2^3
2^6 -----> 8 * 8
2^6 -----> 64

1. 2^12 ----> 2^6 * 2^6
2^12 ----> 64 * 64
2^12 ----> 4096

see the java implementation.

Java

class Solution {
    public double myPow(double x, int n) {
        double ans = pow(x,n);

        if(n < 0) ans = 1.0 / ans;

        return ans;
    }

    private double pow(double x,int n){

       if (n==0)  return 1;

        double ans = pow(x,n/2);

        if((n&1) == 1){

            return x * ans * ans;

        }else{

            return ans*ans;
        } 
    }
}

Time Complexity : O(logn)
Space Complexity : O(logn) for recursion stack

---

Thank you for reading this article. save it for future use.