Easy question can sometimes be very hard and this question is typically belongs to this family. x is integer, n is double. As usual, you should come up with an idea of solving it using recursion. Further, you may want to use memoization when you aware your solution can hardly finish running itself in required time. By this point, I tried to use vector to record the value of every possible pow(x, n) for n starting from 1 to n. However, this fails when n is very very large, say INT_MAX. Because the size is excess the maximum size that is allowed to allocate memory for vector. So, looks like we have to dynamically allocate memory for each subsolution which leads to an idea of using unordered_map and BOOM~, we are done.
Round 2 Solution: Be careful of negative power and overflow. I am also suppressed by how much I improve my code by comparing this solution with my previous one. Practice makes perfect!!!
No comments:
Post a Comment