[Solution]Problem 70: Pow(x,n) [Amazon]
Math, Logic, Optimization, Recursion
To learn more about the newsletter, check our detailed About Page + FAQs
To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.
Get a free Weekly Summary of the important updates in AI and Machine Learning here
Recommend this publication to Substack over here
Take the next step by subscribing here
What is the difference between a guitar and a fish,
You can tune a guitar but can't Tuna Fish. You can thank Google Assistant for that gem. To those of you wondering about the newsletter giveaway, it will happen around the first or second week of Jan. This will give me some time to wrap up some collaborations I’m working on. For more details about the newsletter giveaway, please refer to my announcement post.
Back to the question at hand.
This can be found as Problem 50. Pow(x, n) on Leetcode
Problem
Implement pow(x, n), which calculates x raised to the power n (i.e., xn).
Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000
Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100
Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Constraints:
-100.0 < x < 100.0-231 <= n <= 231-1nis an integer.
-10^4 <= x^n <= 10^4
Step 1: Reading the Problem Carefully
Often when I give this problem to more advanced people, I see their eyes light up. They see the simple solution, so they jump right into it. However, that is a trap and one you must avoid at all costs. Why? It shows that you miss little nuances that mean a lot. You avoid this mistake by reading the problem and conditions very carefully.
Read the problem. Come back. Tell me what the possible trap is. I’ll give you hint. It is an edge case, that you have to consider.
Really gave that one away, didn’t I?
Before you start solving the problem, you have to account for the case 0^0. That is not defined. So how do you deal with it? Ask the interviewer. Remember, asking the interviewer clarifying questions is a very low-risk/high-reward strategy. You should get into the habit of doing so regularly. Based on their answers, you will know what to do. If it’s an online, async assessment, try a few different options to see what works best.
How are we going to approach this? Time for the next step.
Step 2: Handling Base/Edge Cases
Long-term readers saw this one coming. As a general rule, I like to go for the base/edge cases early. I love it for 3 simple reasons-
It allows you to pick low-hanging fruits. The base cases are generally easier to solve.
They sometimes contain hints about the algorithm needed to solve the bigger problem.
This approach looks very fluid and smooth. You’ll look very good in your interview.
In our case, we have the following base cases-
0^0- TBD.
0^n - Should return 0.
1^n- Should return 1.
x^0- Should return 1.
n<0- This is the trickiest base case to solve. How would we do this? This is where we want to go back to math. We know that for a positive number n, x^(-n) will be calculated as (1/x)^n.
For simplicity’s sake, I said that 0^0 was 1. Leetcode accepted it, so I’m not going to overthink it. Our case cases were computed like this-
if not n: return 1
if not x: return 0
if x==1: return 1
if n < 0: x, n = 1 / x, -n
I could have combined 1 and 3 but didn’t to make it explicit that they were different cases.
With this out of the way, let’s move on to the simple solution.
Step 3: Simple Solution
As we always discuss in this newsletter, figuring out a simple brute-force solution is a good step to figuring out the main solution. Often the simple answer is only a few tweaks away from the efficient one.
From a cynical perspective, going from the brute force first also has two other benefits in your interview.
This way you’re always talking, and there is less silence. This can be huge for impressing your interviewer. Especially when you want to buy time to come up with your solution.
By going step by step, you can show a more organized problem-solving approach. This gets those big tech interviewers all hot and bothered and will work in your favor. Going straight to the main solution can make it seem like you have memorized the solution, which is a big turn-off.
The brute force solution here comes straight from the definition of the exponents.
if(n==0): return 1 #x^0 is one
if(x==0): return 0
res=1
for i in (0,abs(n)){
res*=x
}
if(n<0): return 1/res
return resNothing too funky going on here. The second if statement is just a small optimization you can make for a base case. If you want to show off your math knowledge, you can always ask the interviewer what 0^0 should return.
This will not come as a shock, but our current solution is linear time. We can speed it up using some math.
Step 4: Spppeeeedddyyyy Pow
If you have gone through my Math for Computer Science [Math Mondays], you should already be familiar with the basic laws of exponents. We will be relying on that. Don’t worry, we won’t need any fancy algebra here.
Look at the Power Law. It tells us something pretty clean. Instead of multiplying a into itself 8 times, we can multiply a^2 4 times. It should not come as a shock that we can also do a^4 just twice. This is true for all numbers. Here is a quick proof for you.
(a^m)^n= a^m * a^m * a^m (n times)= a^(m*n) by the first law.
Also a^(m*n)= a^n* a^n (m times)= (a^n)^m
Therefore, (a^m)^n = (a^n)^mWe can use this observation to speed up our process. How? We know that if n is an even number, we can write it as 2k. Therefore we can frame this as follows
x^n= x^2K = x^k * x^kWhat about odd numbers? We can write any odd number as 2k+1. This means that
x^n= x^(2k+1)= x* x^2k ...we know where to go from hereFor odd powers, we can decrement our n by one and multiply x with our result. For even powers, we can just square our result and half our n. Pretty neat, huh?
Now it’s time to code everything up.
Step 5: Coding It Up
Putting this together in code, we can do the following code-
def myPow(x,n):
if not n: return 1
if not x: return 0
if n < 0: x, n = 1 / x, -n
result = 1
while n>0:
if n & 1:
result *= x
n -= 1
x*=x
n //= 2
return result
As you can see this problem was not super difficult to code up. Most math-heavy problems are similar. You will be able to code them easily, once you recognize the idea. Most of the heavy lifting is done by recognizing the exponents can be applied in an effective manner.
Time Complexity- O(log N)
Space Complexity- O(1)
Loved the solution? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.
Stay Woke. I’ll see you living the dream.
Go kill all,
Devansh <3
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75