50.Pow(x, n)

Implement pow(x,n), which calculates x _raised to the power _n(x^n).

Example 1:

``````Input:
2.00000, 10

Output:
1024.00000
``````

Example 2:

``````Input:
2.10000, 3

Output:
9.26100
``````

Example 3:

``````Input:
2.00000, -2

Output:
0.25000

Explanation:
2^-2 = 1/2
1/2^2 = 1/4 = 0.25
``````

Note:

• -100.0 < x < 100.0
• n is a 32-bit signed integer, within the range [−2^31, 2^31 − 1]

Thoughts:

1. halve the exponent, squae the input
2. flip the sign of exponent if negative, then inverse the base

1. if the exponent == INT_MIN; change it to INT_MAX,
1. if x is negative, change x to -x before finally inverse it

Sequential Search: T: O(n)

``````class Solution {
public int findPeakElement(int[] nums) {
for(int i = 1; i < nums.length; i ++)
{
if(nums[i] < nums[i-1])
{// <
return i-1;
}
}
return nums.length-1;
}
}
``````
``````class Solution {
public double myPow(double x, int n) {
if(n == 0) return 1;
if(n == 1) return x;
if (n<0){
if(n == Integer.MIN_VALUE){
n = Integer.MAX_VALUE;
if(x<0) x = -x;
}
else{
n = -n;
}

x = 1/x;
}

return n%2==0?myPow(x*x,n/2):x*myPow(x*x,n/2);
}
}
``````