Interesting. This is a problem I used to give to my students over 35 years ago. XD It is the way mainframe computers used to find square roots in the 1930’s and desktop computers did square roots before they got mathematical coprocessors. I wonder if any of my former students sat for an interview. 😁

@maubnesor4702

2 жыл бұрын

According to Wikipedia, mainframes started in the 1950s. The first computers were mostly in the early 1940s.

Yes these are good. I think you guys are doing Basic questions along with specifying category.Please add more questions like this. I like the way you explain.Slow ,Clear,Unambiguous. That shows you have an edge over these topics. Thank you guys :)

Thank you very much, also kudos for pointing out the integer overflow!

In first method only for 1 , 2 and 3 time complexity is o(n) and if explicitly handle these three number then time complexity will become O(sqrt(n)).

Interesting video, nice start to the problem. Just a few quick thoughts on how to optimize for speed and power. While these may not change the Order of complexity it will significantly increase speed and reduce power in the real world. While the number can be from 0 to 1 000 000 000 the square root will only be from 2 to 32 000 so why not search that range? 0 & 1 squared are 0 &1 respectively. Also anything over 32 000 if squared would be over 1000 000 000. Using 32 000 as the max value eliminates the need for a costly divide to avoid overflow. An even faster way would be to first find powers of two which bracket the number. This can be accomplished by simple shifts which are much faster and lower power than even a multiply. The search would be the number of bits, 30 or 5 iterations, 2**5 = 32, give or take. Once you know the number is between 2**2n and 2**2n+2 you can narrow the search. The reason for the 2n is the binary equivalent of decimal squares between 1 and 100 (10**2) which are the numbers 1-10. Once you have the powers of two which bracket the original number 2**2n just start the search at 2**n. Finally using the ratio of the distance between the two powers of two and the number can give you an approximation of what the square root will be, further reducing the search time.

Fantastic explanation!!! Keep it up!!

great video I got the clue of overflow which I corrected. thank you

Very well explained 👌

Instead use mid*mid ik , ik their product will lead integer overflow but idk why they are accepting mid*mid solution, and showing floating point exception in (mid

shaandaaaaaar !!!!!!😁

Won't work with long long idk why floating point exception is the error what it's showing...

Idk why or how we are taking mid start and end while there is no array given...what is given is a number to find square root then why are we taking mid ?

Can you explain why binary search has O(log2n) time complexity ..?

@SCALER

3 жыл бұрын

Hey, you can go through this video on binary search to understand properly about this algorithm: kzread.info/dash/bejne/n2at2qOycqrVhaw.html

madam why not mid*mid

Thanks ❤️

we can search till 1 to n/2 only as sqrt of n will not be greater than n/2

@SCALER

4 жыл бұрын

You're correct, Yash. Similarly, if you know that n is greater than or equal to 10, you can be sure that sqrt(n) will not be greater than n/3. One can continue optimizing this way, reducing the upper limit by a constant multiplicative factor. However, if you consider the practical aspect of things, you will notice that reducing the upper limit from n to n/2 only saves you one additional iteration of the binary search (since binary search would've reduced the n-sized search space by half in the next iteration anyway). Which is why, both asymptotically, and practically, it makes sense to simply work with 0 as the lower limit and n as the upper limit. :)

Nice Voice

why did you do if(mid < = x/mid)? why not if(mid*mid

@iaml2909

Жыл бұрын

i think is to prevent Integer overflow

Thq

got this in an interview and i got struck now here after the interview :D

@SCALER

2 жыл бұрын

Hope this helped clarify your doubt, Sim. :)

Good explanation but didn't worked when tried!

int ans=0; (initializing the variable is imp)

jun k

Hiii mam your voice is so sweet 🙂