Sqrt(x) - Leetcode 69 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
5:50 - Coding Explanation

leetcode 69

#neetcode #leetcode #python

[shafaitahir]

I couldn't think of any solution but got it when you explained the problem in first 50 seconds. Understanding the problem is just as important as the solution.

[NC-]

Great video. One approach to make it compute faster is to continuously divide the number by 2 until you find the lower bound, where lower_bound**2 <= x < (2*lower_bound)**2. Then you perform the binary search, meaning you have a much smaller interval of numbers to go through.

[licokr]

Explanation in detail for beginners. I like how you explain in the part, time complexity. Thanks a lot!

[josemrsantos]

Brilliant video and explanation (as always). Just a small note that (and I am not sure if this was already there, when you first solved it). The problem now states that:

You must not use any built-in exponent function or operator.
For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Not a huge problem as instead of m**2, m*m works just as well

[rojerdu]

Correct me if I'm wrong, but when using binary search to find the square root of a given integer, you never need to check more than half of the value of the given integer. This is because 4 is the only number where the square root is equal to half of the number (4 ** 0.5 == 2). After 4, all square roots become less than half of the square (5 ** 0.5 is approximately 2.236). Moreover, this is more apparent when considering only perfect squares (2 * 2 == 4, 3 * 3 == 9, 4 * 4 == 16). Basically, I believe instead of setting the right pointer = x, you can set it to something like right = x // 2. Please let me know your thoughts.

[Dionmok]

Hi Neetcode, this was a very neat video! One thing to point out is that you disregarded the part of the problem where it says "You must not use any built-in exponent function or operator." Cheers!

[ParthivShah]

One Approach we can Use is that dividing given integer by 2, like m=n/2

r, l = 0, n
m = n/2
res = 0
if abs(r-m)<10:
method --> assume from 1 to 9
elif m**2 > n:
m = m/2 and
minimize range from (0, m)
elif m**2 < n :
r = m/2, l = m
res = m;
return res


If you got this logic then please reply with It's complexity, It may not best solution for small integer but due to It's binary search functionality It can calculate larger values faster( As of My Guess)...Please let me know your thoughts.

[gabrielfonseca]

fun fact: you can do this to approximate the value itself (without rounding down)
Just change the while loop condition to while abs(m * m - x) > 0.001 or something, and don't increment 1 or decrement 1 from m. Also, do float division by 2 instead of integer division to get the new m. This is known as the bisection method.

[niranjandr]

Great approach to solve the problem. However, the code exceeds time limit for certain values. Did slight modifications to calculate the mid as below for which runtime was 29ms beating 96% of users in python3.

if x==0: return 0
left, right=1, x
sqrt_x=0

while left<=right:
mid=(left+right)//2

if mid**2>x:
right=mid-1
elif mid**2<x:
left=mid+1
sqrt_x=mid
else:
return mid

return sqrt_x

[tuandino]

L, r = 0, x
While l<r:
Mid = (l+r+1)//2
If mid**2 < n:
L=mid
Else:
R= mid - 1
Return l

This is more neat

[oliverarmitage]

Hi - Great video, I would recommend anyone writing their solution in C#, C++, Java etc. be careful with types, m*m will cause an integer overflow. You can instead use long.

[akshadabhandari]

Hey, Your videos are very informative and help in logic building. Can you please start making videos for LC daily challenges esp hard problems? would be of great help. Thanks!

[amdbest]

very helpful, i did it in some weird way, but this is better

[micka__to]

Hello Neetcode!
Thanks for the video and for helping us to solve leetcode problems.
I wanted to request to make a video solving 481. Magical String problem, I have been trying to solve it for few days, and didn't do any progress yet. Cannot really get the logic of the question(not the question, but I think if you go to the problem and read it, you will get what I mean by no logic on the question).
Thanks!

[MrLeyt]

you can just calculate the square root of a number in a column
it would be O(1)

[itsthemeg]

class Solution:
def mySqrt(self, x: int) -> int:
i=1
while i<x and x!=0:
if i*i == x:
return i
elif i*i < x:
i+=1
else:
return i-1

this is my code although this runs but does not pass all test cases. Can you tell what's wrong?

[wotizit]

Just got this in my interview and failed miserably :/

[LastVoyage]

No need to write a separate „res“ you can just return „r“

[brendandower]

Doesnt it say in the description that you cant use any built-in exponent functions? ie pow(x, 0.5) in C++ or x ** 0.5 in python. Yet I see you submitted this, so I'm confused how you got this accepted Are they saying that you cant use x^0.5, but you can use x^2?

[TL]

You can use Taylor expansion to solve it in constant time