Problem 2(power_time.py) : find power of a number with constraints as follows
x^n where x is between -100 and +100 while n changes from -10e31 to 10e32 where the power value is always between -10e4 and 10e4. Problem at : https://leetcode.com/problems/powx-n/solution/ Normal solution is either brute force or recursive solution where we use the fact that n can be represented as n//2 and square the result. My solution is to take advantage of the fact that powers are always between 10e4 and 10e-4. This means that we can use a neat formula by always raising to the power e. Represent problem in euler space by using e^(n * log(x)) The problem is solved in near linear time as shown in graph below. This also works well in cases where n is small but x has to be large. |
Archives
March 2022
Categories |