[Solution]Problem 38: Power Function[Stripe]
Math, Logic, Optimization, Recursion
Heyyooo my lovely,
I see you working hard. Kudos!!! Your being tells me how you will invest time into the important things. Give yourself a pat on the back, and we will get into the solution.
Problem
Implement pow(x, n), which calculates x raised to the power n (i.e., x^n). You can’t use any built-in functions aside from basic mathematical operators.
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/2^2 = 1/4 = 0.25 [FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or by Email:
Venmo: https://account.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Or you can sign up for a Free Trial Below. Only 15 days left in this offer -
Step 1: Simple Solution
Since the problem is so straightforward, we can skip straight to the brute force solution. Both the definitions of positive and negative powers are pretty simple. However, as we always discuss on 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 2: 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 any even number, we can write is 2k. Therefore we can frame this as follows
x^2K = x^k * x^kWhat about odd numbers? We can write any odd number as 2k+1. This means that
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. 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)
Make sure you share your thoughts on this question/solution/any interesting questions/developments in the comments or through my links.
Happy Prep. I’ll see you at your dream job.
Go kill all you cyyyoooooolll cat,
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