|
| 1 | +//Instead of using the classic recursive approach i.e. x*pow(x, n-1) just have (x*x), i.e., pow(x*x, n/2). |
| 2 | +//This will make the TC logarithmic instead of linear. |
| 3 | +//Just take care of the edge cases like Integer.MIN_VALUE, negative power, odd cases. |
| 4 | +//Asked in Amazon, Meta, Google, Linkedin, Bloomberg |
| 5 | +classSolution { |
| 6 | +publicdoublemyPow(doublex,intn) { |
| 7 | +if (n==0) { |
| 8 | +return1; |
| 9 | + } |
| 10 | +//Make the negative values positive |
| 11 | +elseif (n<0) { |
| 12 | +//whenever even just divide it by 2 |
| 13 | +//this will also include Integer.MIN_VALUE |
| 14 | +//We're doing this because if I do -N and N=Integer.MIN_VALUE it'll become a value which is greater than the max value of Integer.MAX_VALUE |
| 15 | +if (n%2 ==0) { |
| 16 | +n =n/2; |
| 17 | +n = -n; |
| 18 | +x = (1/x)*(1/x); |
| 19 | + }else {//Odds don't need to be divided as their negative is in the positive limit |
| 20 | +n = -n; |
| 21 | +x =1/x; |
| 22 | + } |
| 23 | + } |
| 24 | +if (n%2 ==0) {//even |
| 25 | +returnmyPow(x*x,n/2); |
| 26 | + }else {//odd |
| 27 | +returnx*myPow(x*x,n/2); |
| 28 | + } |
| 29 | + } |
| 30 | +} |