Power of X to the N LeetCode (Pow(x,n))

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

 Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

 NOTE:

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• -104 <= xn <= 104

This problem is popular in GeeksForGeeks, LeetCode, and is also discussed in other forums, such as Wikipedia, Columbia University A collection of hundreds of interview questions and solutions are available in our blog at Interview Question Solutions

---------------------------------------------------
SOLUTION:
Source code: Java

	/**
	* Implement pow(x, n).
	*/
	package com.alg.leetcode;
	import java.text.DateFormat;
	import java.text.SimpleDateFormat;
	import java.util.Date;
	/**
	* @author rbaral
	*
	*/
	public class Powxn {
	private static DateFormat format = new SimpleDateFormat("YYYY-M-d:H:m:s:S");
	/**
	* @param args
	*/
	public static void main(String[] args) {
	int x=10;
	int n = 3;
	System.out.println(format.format(new Date()));
	System.out.println(myPow(x, n));
	System.out.println(format.format(new Date()));
	System.out.println(myPowNaiveBayes(x, n));
	System.out.println(format.format(new Date()));
	}
	/**
	* though simple, this has TIME EXCEEDS problem
	* the naive bayes approach simply keeps on multiplying
	* x by itself n times
	* @param x
	* @param n
	* @return
	*/
	public static double myPowNaiveBayes(double x, int n) {
	double power =1;
	for(int i=0;i<n;i++){
	power = power*x;
	}
	return power;
	}
	/**
	* this solution uses the recursive approach and has relatively
	* better performance than the NaiveBayes
	* @param x
	* @param n
	* @return
	*/
	public static double myPow(double x, int n){
	//handle the base cases
	if (n == 0)
	return 1;
	if (n == 1)
	return x;
	// keep track of the positive/negative n
	int pn = n > 0 ? n : -n;
	//temporarily store the pn value as we will manipulate the original pn value later
	int pn2 = pn;
	// keep track of the positive/negative x
	double px = x > 0 ? x : -x;
	double result = px;
	int k = 1;
	/**
	* the key part of solving this problem is somewhat similar
	* to the NaiveBayes but here, we multiply for every other
	* increment of the power
	*/
	while (pn / 2 > 0) {
	result = result * result;
	pn = pn / 2;
	k = k * 2;
	}
	//recursively do the computation for the remining power
	result = result * myPow(px, pn2 - k);
	// handle negative result
	if (x < 0 && n % 2 == 1)
	result = -result;
	// handle negative power
	if (n < 0)
	result = 1 / result;
	return result;
	}
	}

view raw PowerNofX.java hosted with ❤ by GitHub