Pow(x, n) - X to the power of N - Leetcode 50 - Python

0:00 - Read the problem
1:40 - Drawing Explanation
7:40 - Coding Explanation

leetcode 50

#amazon #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[jjjjjj]

I got this one in an interview.. 20 minutes to solve it. It did not go well. Lessons learned:

1) Mention but do not code obvious solutions without getting buyin (it wastes time). A big company is not going to hire you because you can write a loop.
2) Don't necessarily ignore a leetcode problem because it is downvoted a lot. It doesn't mean it's unpopular.
3) a log n solution usually means binary search or some sort of divide and conquer. Even if you get that quickly crafting a bug free recursive solution to this one is tricky. A bit hard to do well unless you've seen it already.

[RolopIsHere]

5 minutes before my interview I saw this video, and it was this question... lucky. It even gave me time to solve it using bit manipulation.

[dharani]

Thanks a lot for this! People out there were explaining the solution but not the idea behind it! Thanks a lot

[mirzasohailhussain]

I love it, the way you just said, instead of writing 2 multiply by 10 times, can't we just multiple twice 2 by 5 times. i got the logic. thank you so much. This is addiction.

[Wes-Tyler]

It has a lot of downvotes because the description is terrible. It wants you to use a log(n) solution, but it never tells you that. Instead it implements an overly restrictive time limit that forces O(n) solutions to fail, and the O(log n) solution is completely unintuitive and no one would know it unless they have read the solution before or they're a mathematician.
Also the problem never once specifies if you need to worry about fractional exponents or not. In this case you don't, but the description should have said that in the constraints (n will always be an integer, for example, would be one way to say it).

[suketu]

recursive solution takes log(n) space. use iterative solution for O(1) space

[HR-pzts]

6 mins in and you already told me the mistake I was making. I was doing return pow(x, n/2)*pow(x, n/2) which was making two rec calls. But you said it'll make only one call and i had that aha moment and stored the result in a var.

[tiyaaaa]

I think the two base cases need to swap, cause the 0 power of 0 is 1 instead of 0, but it will also pass cause there is no test case in leetcode itself.

[utkarshpune]

Iterative solution
def powIterative(x, n):
if n < 0:
x = 1 / x
n = abs(n)
res = 1
prod = x
while n:
if n % 2:
res = res * prod
prod = prod * prod
n = n // 2
return res

[mohammedkssim]

There is a small problem in what you have done. 0 power 0 is equal to 1 not 0, so if x==0.0 and n==0 the output should be 1 not 0 as you mentionned as a best case. I guess the code you have provided passed the test because there was no 0 pow 0 test case.
Thank you a lot for your help !

[pawananubhav]

it works the same way if we dont use absolute of n(in helper function), because we ralready checking later if n is positive or negative and then tweaking the result therefore using abs of n is redundant.
great solution tho!

[dyistopia]

If you convert this to iteration, you can lower the space complexity to O(1) as it eliminates the need for the recursion stack

[gabrielfonseca]

Iterative solution:

initialize power to 1
initialize current_multuplication to x
Initialize boolean negative that is true if n < 0
let n = abs(n)
let final_multiplication = 1

loop until n == 0:
find the largest power of 2 exponent by repeatedly squaring current_multiplication and doubling power
multiply final_multiplication by current_multiplication
subtract the largest power (the variable power) from n and reset power and current_multiplication (to 1 and x)

Example:
x ^ 15 = x ^ 8 -> n is now 15 - 8 = 7
x ^ 7 = x ^ 4 -> n is now 3
x ^ 3 = x ^ 2 -> n is now 3 - 2 = 1, then 1 - 1 = 0 so break out of loop

Can possibly make this faster by caching results, but you wouldn't know the next largest power on the first pass without a logarithm function which would defeat the point. Either way the it would be log(n) runtime

[octolocus]

class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1

elif n < 0:
return self.myPow(1/x, -n)

if n % 2 == 0:
temp = self.myPow(x, n/2)
return temp * temp

else:
return x * self.myPow(x, n - 1)

#faster than 90% solution

[MalushJ]

the naive solution is not linear, its exponential. When looking at n you have to look at the asymptotic growth of n. If this was a list then yes linear would be the answer but because we are dealing with an integer we have to look at the input "size" in this case, it take k = log(n) number of bits to represent n. So if we look at the number of bits as the rate of our input size growth we get O(2^k) as the run time. So the Pow(x, n) naive solution is exponential and the divide and conquer (more optimized) method is O(k) because k = log(n). So that makes the optimized solution the actual linear run time here.

[IgorGuerrero]

My cursed solution after a bit of researching:

class Solution:
def myPow(self, x: float, n: int) -> float:
if n < 0:
x = 1 / x
n = -n
result = 1
while n:
if n & 1:
result *= x
x *= x
n >>= 1
return result

It's a lot less understandable.

[dallasmilanista]

When x=1, we can consider this as a base case too right? Since 1 to the power of any n will give 1?

[Cloud-]

if you are getting incorrect output for python try wrapping the final output with float before returning

[rvs]

Finally I could solve this problem in c# with less code than python 😂😂

public double MyPow(double x, int n) {
if (x == 0 ) return 0;
if (n == 0 || x == 1) return 1;
var res = MyPow(x * x, Math.Abs(n/2));
res = n % 2 == 0 ? res : x * res;
return n < 0 ? (1/res) : res;
}

[FRANK-dkbc]

100% beats
class Solution(object):

def myPow(self, x, n):
if n%2==0:
num=x**(n/2)
return num*num
elif n%2!=0:
num=x**int(n/2)
return num*num*x