Find power of a number
Ninja is sitting in an examination hall. He is encountered with a problem statement, "Find ‘X’ to the power ‘N’ (i.e. ‘X’ ^ ‘N’). Where ‘X’ and ‘N’ are two integers."

Ninja was not prepared for this question at all, as this question was unexpected in the exam.

He is asking for your help to solve this problem. Help Ninja to find the answer to the problem.

Note :

For this question, you can assume that 0 raised to the power of 0 is 1.

Input format :

The first line of input contains integer ‘T’ denoting the number of test cases. Then each test case follows: The first and only line of each test case contains two integers ‘X’ and ‘N’ (separated by space).

Output Format :

Output will contain a single integer which will be equal to X ^ N (i.e. X raise to the power N). Output of each test cases will be printed on separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Find power of a number

Ninja is sitting in an examination hall. He is encountered with a problem statement, "Find ‘X’ to the power ‘N’ (i.e. ‘X’ ^ ‘N’). Where ‘X’ and ‘N’ are two integers."

Ninja was not prepared for this question at all, as this question was unexpected in the exam.

He is asking for your help to solve this problem. Help Ninja to find the answer to the problem.

Note :

For this question, you can assume that 0 raised to the power of 0 is 1.

Input format :

The first line of input contains integer ‘T’ denoting the number of test cases. Then each test case follows:

The first and only line of each test case contains two integers ‘X’ and ‘N’ (separated by space).

Output Format :

Output will contain a single integer which will be equal to X ^ N (i.e. X raise to the power N).

Output of each test cases will be printed on separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
0 <= X <= 10
0 <= N <= 10

Time Limit: 1 sec.

Accepted Answer

Recursion

The approach is to recursively call the recursive function for X and N - 1 and multiplying the value returned by the recursive function with X.

As X ^ N is same as X * (X ^ (N - 1)).

Approach :

First, let's say the recursive function is ‘POW(X, N)’ having ‘X’ and ‘N’ as arguments.
The base case for the recursive function will be for N = 0 to return the value 1. As X ^ 0 = 1 and for X = 0 to return the value 0.
Now call the function recursively with ‘X’ and ‘N - 1’ as arguments and return the value to the function by multiplying the value with ‘X’.
- return X * POW(X, N - 1).

Space Complexity: O(1)Explanation:

O(1)

As we are using constant space. Therefore, time complexity will be O(1).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the given number.

As, we are making recursive calls N number of times. Therefore, overall time complexity will be O(N).

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(1)

    Where 'N' is the given number.
*/

public class Solution {
	public static long Pow(int X, int N) {

		// Base Case X ^ 0 = 1
		if (N == 0)
			return 1;

		// 0 ^ N = 0
		if (X == 0)
			return 0;

		// X ^ N = X * (X ^ (N - 1))
		return X * Pow(X, N - 1);
	}

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where 'N' is the given number.

*/



long long Pow(int X, int N)

{



    // Base Case X ^ 0 = 1

    if(N == 0)

    {

        return 1;

    }



    // 0 ^ N = 0

    if(X == 0)

    {

        return 0;

    }



    // X ^ N = X * (X ^ (N - 1))

    return X * Pow(X, N - 1);

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where 'N' is the given number.

'''



def pow(X, N):

	

	# Base Case X ^ 0 = 1

	if(N == 0):

		return 1

		

	# 0 ^ N = 0

	if(X == 0):

		return 0

		

	# X ^ N = X * (X ^ (N - 1))

	return X * pow(X, N - 1)

Accepted Answer

Optimized Approach

In this approach, we will call the recursive function for ‘X’ and ‘N / 2’. As X ^ N is same as

( X ^ (N / 2) ) * ( X ^ (N / 2) ) for N being an even number and X * ( X ^ (N / 2) ) * ( X ^ (N / 2) ) for N being an odd number.