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

[@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.

[@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

[@gamer_bhai259]

for 1 all write differently ri8>\]

[@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

[@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

[@adarshkumarrao3478]

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

[@indroneelgoswami5654]

I solved this question without watching the video!!! OMG!!! STRIVER YOU BEAUTY!!!!!!!!!!!!!!!

[@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.

[@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

[@souviksen7345]

Always top level concept clearer ❤

[@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.

[@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?🤣

[@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

[@vedikamishra009]

@@abhimanyushekhawat2626 for n=2 the answer is 1, if you carefully observe low = 1 high = 1 and mid is also 1*1

[@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.

[@saireddyreddy8969]

Your explanation is just awesome.

[@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; }

[@lucario404]

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

[@SuvradipDasPhotographyOfficial]

amazing explanation striver, understood.

[@subhankarkanrar9494]

Respect to Striver ❤ for such a easy explanation

[@KarthikNandam-xs4qn]

use the check value as if( mid

[@oyeesharme]

thanks bhaiya for your endless efforts

[@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

[@higgsboson67]

​@@himanshukamble765 what about n=2 ?

[@thanos8323]

@@higgsboson67 for n=2 the answer is 1, if you carefully observe low = 1 high = 1 and mid is also 1*1

[@manavsingh5919]

Thank you Striver...Understood everything🙂

[@AtulKumar-c4x7l]

understood.. Thank you striver for such an amazing explanation

[@AbhiSharma-ku7dq]

Thank you for creating such courses

[@ashishpradhan6250]

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

[@tripd4949]

Wow that was a very slick approach, good job.

[@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.

[@Manasidas99]

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

[@cinime]

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

[@parulvats]

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

[@hareshnayak7302]

Understood, Thanks striver for this amazing video.

[@SatyaPrakash-dj8ix]

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

[@shreyanshkumar4528]

Just awesome explanation.

[@VishalGupta-xw2rp]

10:50 Opposite Polarity Lec 12, 13 also has

[@graviton001]

Was able to do it myself thnx ❤

[@umairislam505]

You are awesome brother

[@mcbotface]

Largest integer or smallest integer are correct terminologies.

[@sushantguria8820]

Understood 🤘

[@srilathareddy9450]

Superb explanation

[@biryanibroseph210]

awesome explanation sir

[@lshuarckyma]

STRIVERS TIP = if one part of a vector / data strc can be fully eliminated from consideration then binary search can be used

[@manusklm1161]

checking if the (mid*mid==x) and returning mid before the actual "check" makes the code more efficient . am i right?

[@Josuke217]

Binary Search on answers finally !

[@DeepakPatel-d5v]

Thanks a lot Bhaiya

[@avisoft-l2p]

if we take high as n/2, then also we will get a desirable ans! US bhaiya

[@RaunitJaiswal-s9v]

Started 2 video karke sojaynege bhaya 😮😮

[@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

[@AnmolGupta-oj4lm]

Understood Very Well!

[@ishasingh6726]

Thank youuu striver❤

[@sukhpreetsingh5200]

❤Awesome as usual

[@Spavan3011]

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

[@kumarshivam3661]

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

[@EC20022ELAKKIYAC]

Understood!!! Thank You

[@NazeerBashaShaik]

Understood, thank you.

[@utsavseth6573]

Understood RAJ.

[@amanasrani6405]

Understood Bhaiya

[@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.

[@livinkumarsaravanan3781]

Worth content 👍

[@sparrow_harsh]

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

[@Aditi-do4im]

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

[@PrioritizingPeace]

27 July 2024 Saturday 10:42 PM done ✅

[@pradipkumarmukhi]

Understood 😇

[@YourCodeVerse]

Understood✅🔥🔥

[@UddhikaIshara]

Thank you very much

[@DeadPoolx1712]

UNDERSTOOD;

[@vigneshlion9309]

great video!❣

[@syedFAHIM-el1wr]

Thanks you a lot, Can't thank enough

[@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 😞😞😞

[@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?

[@hrushi_borhade]

Understood striver!!

[@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.

[@Omi69-l4q]

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

[@SYCOA12CHAITANYAASOLE]

Understood !! 😎😎

[@kushagramishra5638]

understood!

[@md.imrankhan6912]

Legendary boss

[@senseiAree]

Understood ❤

[@arihantjammar8888]

UNDERSTOOD

[@ambaradhikari7425]

waiting for linked list, bit manipulation and strings please

[@MohammedHasmi577]

❤❤great video bro

[@parassetia4964]

Understood boss^^

[@sarangkumarsingh7901]

Understood.......

[@RaviKumar-sn6tu]

understood!!

[@meghasharma4875]

can i take low 1 and high n/2 beacuase square root of any no. never touch nth position

[@navneetrai9512]

yes, bcz squrt of any number can't be grater than or equal to 'number/2 '

[@mehedihasansabbir7886]

Superb

[@raholsaha8191]

great video

[@rajashekar9912]

Bhaiya plz start linked list series

[@priyeshtandel2101]

Understood

[@DineshC-d8p]

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

[@HARSHRAJ-wz2rp]

The demand of Levis Tshirt increses from Tomorrow

[@harshitjaiswal9439]

Understood!

[@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

[@AbhishekBhattacharjee-j2m]

UNDERSTOOD

[@thedominatorscircle6762]

Bhi logic kayse build Karu kuch batao plzzzz

[@crazymemes4080]

Understood bhayaaaaaaaa

[@roshangupta1686]

underatood

[@humanity7880]

understood!

[@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

[@dreamyme543]

Understood🙃

[@AmanKumar-qz4jz]

thank u sir