BS-10. Finding Sqrt of a number using Binary Search

Problem Link: bit.ly/3J5dBCJ
Notes/C++/Java/Python codes: takeuforward.org/binary-searc...
We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
0:00 Introduction of Course

[@varun1017]

The check "mid * mid

[@anigaming7146]

Thanks bro😊

[@varun1017]

@@anigaming7146 welcome

[@pushankarmakar1783]

thanks brother, i was also thinking of the same issue but since there were no errors in the testcases so i ignored it. they can bring up this issue in an interview

[@varun1017]

@@pushankarmakar1783 all the best

[@harshitrautela6585]

Thanks for help.❤❤

[@piyushraj5464]

Had been desperately waiting for the series to restart. Thanks a lot.

[@Dipanshutripathi2407]

Hats Off to the content and it's creator ! Understood each and every part of the video.

[@Manishgupta200]

Good to see from brute force approach to optimal approach.

[@cinime]

Understood! Awesome explanation as always, thank you very very much for your effort!!

[@souviksen7345]

Always top level concept clearer ❤

[@saireddyreddy8969]

Your explanation is just awesome.

[@tripd4949]

Wow that was a very slick approach, good job.

[@user-ti3bd8mp1w]

understood.. Thank you striver for such an amazing explanation

[@SuvradipDasPhotographyOfficial]

amazing explanation striver, understood.

[@ashishpradhan6250]

understood clearly...thanks a lot, u have given me hope!

[@manavsingh5919]

Thank you Striver...Understood everything🙂

[@adarshkumarrao3478]

Excellent explanation ❣.. Waiting for linked list series💛💛

[@Manasidas99]

Great video you made thank you very much sir waiting for the linked list Video.

[@shreyanshkumar4528]

Just awesome explanation.

[@hareshnayak7302]

Understood, Thanks striver for this amazing video.

[@AbhiSharma-ku7dq]

Thank you for creating such courses

[@thetechmasum]

using the concept of lower bound : private static int getSquareRoot(int n) { int low = 1; int high = n; while (low(long)(n)){ high =(int) mid-1; } else { low =(int) mid +1 ; } } return low-1; }

[@srilathareddy9450]

Superb explanation

[@pragathid7743]

awesome explanation sir

[@AnmolGupta-oj4lm]

Understood Very Well!

[@subhankarkanrar9494]

Respect to Striver ❤ for such a easy explanation

[@sukhpreetsingh5200]

❤Awesome as usual

[@lucario404]

we can check sqrt from 1(low) to n/2 (high) as well

[@iWontFakeIt]

first naive approach had TC of O(sqrt(n)) but binary search has TC of O(log(n)) which is eventually slightly better than former one for very large values.

[@mayankshakya9200]

Correction at time 12:45 the time complexity of the brute force solution is not O(n) as suggested by striver but it is O(sqrt n) according to me as the loop will break after that condition always And plz striver bhaiya vidios jaldi jaldi daal do bhot wait kar liya

[@champion5946]

thodi sharam kr... wo banda full time job me itna kr rha h... patience nhi h logo ko free ki chizz bhi jalid chaiye

[@mayankshakya9200]

@@champion5946 chal na lavde aa thuu maine mana kiya kya ki wo efforts nahi maar raha striver ke liye 1000 percent izzat hai mere dil me and mere msg ka wo matlab nahi tha

[@kumarshivam3661]

​@@champion5946are didi placement hai next month se isliye thoda patience nhi rakh paa rhe log

[@suyashmishra6946]

Understood!! Here are the time stamps: 00:00 - 00:15 Intro 00:16 - 1:15 -Problem description 1:16 - 4:00 - Brute(linear) 4:01-5:20 - Binary search intuition 5:20 - 16:16 - Optimal solution 16:17 - 16:45- code 16:45 - 17:10 - outro

[@Shanky_17]

Why bro? just why ??

[@hoang640]

@@Shanky_17 Just love him for that

[@NazeerBashaShaik]

Understood, thank you.

[@ishasingh6726]

Thank youuu striver❤

[@jasrajsehmbey]

You can also take high as n/2 rather than n intially as it is certain that ans will lie in a range of 1 to n/2

[@takeUforward]

Yes

[@uditgarg6508]

i did the same initially

[@EC20022ELAKKIYAC]

Understood!!! Thank You

[@syedFAHIM-el1wr]

Thanks you a lot, Can't thank enough

[@livinkumarsaravanan3781]

Worth content 👍

[@vigneshlion9309]

great video!❣

[@UddhikaIshara]

Thank you very much

[@user-or5oz1pk2x]

Thanks a lot Bhaiya

[@Aditi-do4im]

you r incredible !!!!!!!!!!

[@sudhanshushekhar4222]

Understood; but to be noted we can also take low = 1 and high = n/2 this also works because sqrt of a number is always less than or equal to n/2. But I guess here it do not matter as this will only reduce one iteration but if we are dealing with a program which regularly calculate the sqrt these one one iteration which is reduded might sum up and save a lot of time..[ just a random thought]

[@abhimanyushekhawat2626]

What about 2?

[@dhruvchopra26]

@@abhimanyushekhawat2626 Works for 2 as well.

[@artifice_abhi]

just right an if condition at the start @@abhimanyushekhawat2626

[@pushankarmakar1783]

dada, cant we optimize it further by reducing the search space. we can keep high as n//2 initially cause a square root of a number can never be greater than half of the number.

[@VishalGupta-xw2rp]

10:50 Opposite Polarity Lec 12, 13 also has

[@YourCodeVerse]

Understood✅🔥🔥

[@parulvats]

In pseudo code it was mentioned either we can return ans or high, but returning ans giving error

[@sohamchatterjee6934]

I aam doing dsa from tha last 6 months and i found u yesterday and now i am a fannnn...

[@DR-mq1le]

hows your dsa prep going now , i just started , does it get any better?🤣

[@impalash_ag]

Hi Raj, I think the solution can be bit more efficient with the TC of O(log n/2) instead of O(log n). Since, we know square root of any number n can't be bigger than half of that number i.e, n/2 therefore we would take high as n/2 instead of n. Here's the code: class Solution { public int mySqrt(int x) { if(x == 1) return 1; int low = 1, high = x/2; int result = 0; while(low

[@Josuke217]

@@impalash_ag good observation

[@himanshukamble765]

yup i also thought of that

[@amanasrani6405]

Understood Bhaiya

[@sparrow_harsh]

Can you come up with a video where we need to find square root upto decimal precision p

[@raholsaha8191]

great video

[@MohammedHasmi577]

❤❤great video bro

[@hrushi_borhade]

Understood striver!!

[@user-is6ky7pp2n]

Understood !! 😎😎

[@Josuke217]

Binary Search on answers finally !

[@user-nb1ye5tf1r]

Understood

[@md.imrankhan6912]

Legendary boss

[@thenriquevicentini]

Understood!

[@utsavseth6573]

Understood RAJ.

[@senseiAree]

Understood ❤

[@mcbotface]

Largest integer or smallest integer are correct terminologies.

[@kushagramishra5638]

understood!

[@sarangkumarsingh7901]

Understood.......

[@crazymemes4080]

Understood bhayaaaaaaaa

[@mehedihasansabbir7886]

Superb

[@kumarshivam3661]

Striver Bhaiya please august end tak a to z sheet complete kra do

[@RaviKumar-sn6tu]

understood!!

[@VineetKumar-fk2rl]

Understood❤

[@rhul0017]

if we find the sqrt of 9 then, i found that the high wont point to last valid integer, only when low crosses high,high points to 3, is this same for others?

[@VishalGupta-xw2rp]

If you observe then we don't really have to take high = n Because in all the cases we are only going till half of n.... Sooooo I think we can further reduce our search space 1 to n/2 and then apply binary search 👨‍💻

[@muskan_bagrecha]

Right. Although even if you start with n, the first partition will end up dividing it into half. So should not make a huge difference. Also if you are considering n/2, we need to make sure we are not rounding down values like 1.

[@arihantjammar8888]

UNDERSTOOD

[@Spavan3011]

What if we have to find exact ans not an integer?

[@parassetia4964]

Understood boss^^

[@AmanKumar-qz4jz]

thank u sir

[@dhairyachauhan6622]

bhaiya please ek series bitmasking pe bhi bna dena. I know you already are busy.But jab ye playlist khatam ho jaye aur time mile then plese consider. If you have any recordings/ suggestions on how to learn toh please ek bar bta dena 😞😞😞

[@ambaradhikari7425]

waiting for linked list, bit manipulation and strings please

[@mrsttechno5974]

Understand

[@dreamyme543]

Understood🙃

[@sumanth2888]

understood

[@kiransoorya7895]

Bhaiya why can't we use high as n/2 instead of n at start in the function(instead of 28 we can use 14 ) 13:14

[@nayankhuman1043]

Understood :)

[@rajashekar9912]

Bhaiya plz start linked list series

[@SatyaPrakash-dj8ix]

this is somewhat similar to Newton-Raphson method we use in engineering mathematics.

[@roshangupta1686]

underatood

[@pihus3498]

understood :)❤

[@keshavbiyani9202]

can someone explain how is linear O(N) ?? It will always be O(sqrt(N)) only right ?? Because for 28 we at max take 6 iterations.

[@thedominatorscircle6762]

Bhi logic kayse build Karu kuch batao plzzzz

[@Icelander00]

Thanks

[@undextered]

Great

[@astroop1528]

Can someone tell me why my code is giving wrong answer. int floorSqrt(int n) { long long s = 1, e = n; long long ans = 1; while(s

[@akbunofficial1281]

Hey!, can anyone tell , why this code is not working in one of the test cases of coding ninjas,(actually , i am unable to find that test cases on coding ninjas), but it is passing all test cases on gfg, if anyone can figure out?

[@Simran-ns8gp]

Check the data type..mine was also not wokring but then I changed the data types to long long , it passed all the test cases

[@muskan_bagrecha]

mine was failing for n = 1, as I had my upper bound at n/2 which was rounding it down to 0.

[@jimmy-qq78]

@@Simran-ns8gp i also changed but it is not working pls tell

[@mihirkumar4770]

int mySqrt(int n) { if(n==0)return 0;if(n==1)return 1; int ans=-1; int start=1;int end=n/2; while(start

[@352_sanyajain4]

nicee

[@BiswajitDas-fj5gp]

❤❤❤

[@Vishnu-zk2nm]

Which notes app you are using ???

[@motabhaimotivation]

"good notes " that comes in ipads

[@princepandey1836]

bhai ans return krene pr 1 test failed hora. but high pe all test cases passed. can someone tell me why?(coding ninjas). also int ans ; or int ans = 0; --> EVery test case passed but, int ans = -1 or 1. one test case failing why

[@srj8dmusic699]

First View ❤🎉

[@nikhilkumarjamwal5322]

square root with precision ???

[@official_madhusudan_chauhan]

Present Sir 25th/06

[@-ShangsitNath]

What is the issue in this code?? int floorSqrt(int n) { // Write your code here. int ans=-1; int s=1, e=n; while(s

[@bytesage-he8pd]

Same for me. Test cases are hidden also

[@bytesage-he8pd]

The two corner case are n == 0 and. n == 1 add check for them it will pass. Thanks @mihirkumar4770

[@user-tk9ks8rs4g]

in this problem why we use binary search because we do in o(1) --> { ans=(n**0.5) ans=SquareRoot value } anyone explain why we go with binary search. Thanks

[@lucifersamrat6280]

just to test our problem solving skills

[@girikgarg8]

Done

[@aakashbhandari9761]

What is the number is not perfect square??

[@girikgarg8]

@@aakashbhandari9761 Return the floor value i.e. nearest integer to the left

[@aakashbhandari9761]

@@girikgarg8 means if the number is 28 we should return 5.0??

[@user-uv5or5bm2c]

UnderStood

[@cenacr007]

us