-
Notifications
You must be signed in to change notification settings - Fork 0
/
50. Pow(x, n)
29 lines (29 loc) · 975 Bytes
/
50. Pow(x, n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//🎯DAY 25 PROBLEM 1
//EDGE CASES TO BE CONSIDERED: the range of int is -2^(31) to 2^(31)-1 so abs(-2 ^(31)) goes out of range of int so we use long long
//The idea is to use log(n) time complexity for rate of decrease of n as that is what constraints allow.
//If we have to calculate 2^(10), 2^(10)=> (2*2)^5 => 4^(5)=>4 * 4^(4)=> 4* (4*4)^2=> 4* (16)^2 => 4* (16*16)^1, we reached base case and we keep on returning 256 upwards
//and once multiply it by 4.
class Solution {
double pow_calc(double x,long long n)
{
//to be dealt explicitly
if(n==0)
return 1;
if(n<=1)
return x;
if(n%2==0)
return pow_calc(x*x,n/2);
else
return x*pow_calc(x,n-1);
}
public:
double myPow(double x, int n) {
long org_n=n;
n=abs(n);
double ans=pow_calc(x,n);
if(org_n>0)
return ans;
else
return (double)1/(ans);
}
};