Nth Root of a Number Using Binary Search

[@takeUforward]

Instead of multiplying by running a for loop, we can use Binary Exponentiation technique to do in log N. Video: kzbin.info/www/bejne/omG8dGZubJukrsk

[@secondguy]

so sir, should the time complexity be logN*log(M*10^d)??

[@pranavgawade1546]

You shoud not sacrifise your sleep for this.

[@Usurperhk]

Can't believe you work late nights to deliver quality content in community. That's what makes you different and an inspiration to many students.

[@Ben10qz]

Fun fact : Scalar is showing their add here also in between the video !

[@Mr_SSK]

We can reduce the search space by taking 'high=m/2' initially. But, here we need to handle the case of n==1 explicitly, that means when n==1 ( we want the 1st root of m) we have to directly return m. We won't go for any calculations. -> We can set high=sqrt(m) as well, but in that case you have to make sure the sqrt() returns double (instead of int) Anyways, AMAZING EXPLANATION! 💜🙏

[@vanshikagarg489]

Overall complexity is N Log(N) by doing... We can also count the the number of element which are smaller than mid in O(n + n ) . Instead of doing binary search on every row we can compare last element of every row if it it smaller than mid we take count of row size or if it is greater we can traverse the row by back until elem is bigger than mid. This takes O( n + n ) time.

[@vanshsehgal9475]

what do you mean by row?

[@lifegood6401]

1 clock waali baat ne emotional kr diya. Great Explanation. Mja aa jata hai aapki videos dekh kr. I am confident i am going to do good in placements if i finish this series honestly

[@sanbidrc]

We can never thank you enough for such amazing content.

[@OatsAurCode]

DP series is helpul. Somehow the code not passing all the test cases in gfg. So adding a working code. That might be helpful class Solution: def NthRoot(self, n, m): # Code here if m == 1: return 1 if n==0: return 1 if n==1: return m start = 0 end = m//2 while start

[@bhaveshkumar6842]

There's nobody like you, Striver. You're the BEST!!!!

[@govindsharma7696]

Bhaiya aap jadugar ho , kya samjhate ho mashallah ❤️❤️

[@AbidAhsan-yp4dc]

this is the best explanation of the problem you can find on entire internet . thanks a lot

[@jayachandra677]

I thought this would be just like mid*mid == n but I didn't know that decimal thing. Also I blindly thought that the time complexity will be O(n*log(n)). Thanks for the video bhaiya!!!

[@amarks444]

i am watching this video at 2:04am 🥱 , and when i heared "recording video at 1:00 am and sleep at 4:00 am after editing" , my energy get boosted 😎🤩 ....

[@senpaidawwwggg]

2:51 LoL

[@arnabghosh9632]

We can use binary exponentiation or can use inbuilt pow function to calculate the power this will reduce the TC to O(LogN * log(M*decimal*10)

[@akankshamaurya9219]

But using inbuilt pow function ,it is not passing all test cases

[@immortal4412]

@@akankshamaurya9219 it is working check in gfg practice

[@pratyushbhatt1712]

Great!! You can further optimize the solution to a much greater extent bdw. When using the multiply function, you are using a very naive technique to calculate the Power, instead we can use Binary Exponentiation, which is logarithmic in nature. That will fasten it up. Great explanation bdw.

[@takeUforward]

Yeah I have mentioned in the pinned comment :)

[@pratyushbhatt1712]

@@takeUforward yeah just saw that.. Anyways, great content as always.

[@aandz6194]

@@takeUforward Im little confused because..... Either we get the root of the number don't we check until 10^(-6)....... So what will be time complexity now in the worst case.....?

[@sonuGupta-vo8vm]

Always learn new concept . And you makes CP more interesting . I likes your way of explaining time and space complexity. Thanks

[@kartikgarg9379]

Bhaiya your graph series is amazing and those dry runs are awesome thanks bhaiya

[@RamKumar-kz8gg]

enjoy

[@411_danishranjan9]

why you take low = mid, why not low= mid+1 and high = mid, why not high = mid-1

[@deepraj2631]

As you can see that he took 1 base indexing not zero base indexing, hope you can get the idea why it's happening so

[@harshabellamkondasrinivasa4527]

omg.....4'o clock in the morning.... hats off to ur dedication sir. Can't thank u enough

[@parthparmar9798]

this is what I want. an amazing playlist for Binary search.

[@jothamprince8765]

thanks man, u just saved me from failing my class assignment, i've been trying to crack that for 3 days

[@krishnakumar-rp9wc]

can we use pow instead of multiply function?

[@kaichang8186]

understood, thanks for the great explanation

[@ReD4eva94]

I have seen a lot on youtube. You are the very best.

[@harleenkaur7751]

Thanks a lot striver. We always learn a new concept through your lecture.

[@prithvichetty15]

Best Explanation of Binary Search. Eagerly Waiting for your Tree Series!!!❤❤

[@yeswanthh5068]

Thank you sir understood

[@harshitvarshney2627]

Great Explanation bhaiya Bhaiya....please make a playlist on the tree as well.

[@cpwithsundar]

There is no match for your hardwork , but we too would work hard even if it doesn't surpasses yours.

[@dayanandraut5660]

Great explanation around intuition building and time complexity. Keep it up bro

[@manavmalhotra8513]

public class Solution { public static double findNthRootOfM(int n, long m) { // Write your code here. double lo=1; double hi=m; double eps=1e-7; while((hi-lo) > eps){ double mid = (lo+hi)/2.0; if(multiply(mid,n)

[@dipanshusharma9084]

make these changes cout

[@muhsinmansooriee_0017]

@@dipanshusharma9084 why did we do this? as it is asking in the question to check for up to 6 decimal points.

[@dipanshusharma9084]

@@muhsinmansooriee_0017 because in the ans it was taking upto 9 decimals , there was mistake in test cases

[@prakharanand7778]

because when you are passing the argument to the multiply method, you are storing mid in parameter n and n in parameter m method call. But you are running the for loop inside multiply() n times which actually is mid due to your incorrect argument order during method call. fix it and your code will work just fine.

[@gather.in.coding.lounge]

You are just doing all the way great, I really thank you for all these wonderful playlists.

[@prakharanand7778]

In time complexity from 1 to say 27 there aren't 10*27 real numbers for upto 1 decimal place. 1.0 1.1 1.2 .... 1.9 (10 nos) 2.0 2.1 ... 2.9 (10 nos) ... 26.0 26.1...26.9 (10 nos) total nos till now = 10*26. And one more number 27.0 which makes the total real numbers from 1 to 27 equal to 10*26 + 1 => (M-1)*10 + 1? If no please explain.

[@parthkabra8880]

no words, excellent explanation

[@RohitKumar-dy2gc]

u r so dedicated man i wanna be also that much

[@AkshayKumar-kp2ye]

My thought process went towards the mathematics approach initially. Wasn't able to deduce the binary search approach on this. Thanks for the video bro. double findNthRootOfM(int n, int m) { // Write your code here. return exp(log(m)/n); }

[@antiquefood6284]

Recently asked in Apple Interview to my experienced brother !!!

[@shaamidrees6036]

amazing explaination as always Thanks

[@yogeshyts]

double t=1.000000/n; double ans=pow(m,t); return ans;

[@monkeeys23]

hey striver could you make a video for a non engineering background student to start coding journey and get into top companies road map sort of thing

[@RamKumar-kz8gg]

watch love babber video

[@ShwetaSingh-qw7mo]

great explanation

[@amitzerikunthe7635]

hats off to ur dedication 🙏

[@Ballistic_Bytes]

A much simpler method of solving it would be to just use log and antilog. Following is a TypeScript Solution:- const nthRootOfM = ( n: number, m: number, ): number => Math.exp(Math.log(m) / n);

[@harshitsaxena7205]

do you have any question on std platform please provide me for practise

[@jayadubey_22]

keep educating bhaiya nicely explained

[@sourabhchoudhary7289]

why can't we put an extra condition for multiply(mid,n)==m then return mid?

[@SudhanshuKumar-lp1nr]

Because it will take a lot more iteration to become equal to root(M).

[@srijitmondal4190]

@@SudhanshuKumar-lp1nr why? We are not putting the condition inside while loop instead we are putting this as an extra if()

[@sauravkumargupta2594]

Ye jo unlike krne wale hai na... Unka mental level hi nhi itni asan videos ko smjhne ka 😂😂

[@s.g.prajapati3597]

Great content bhaiya! Learned and understood to the fullest!

[@willturner3440]

Sde sheet become interesting day by day

[@aaaa-pr2dd]

😳awesome dada, didn't knew to use binary search this way

[@saurabh44gupta]

Hi, I want to know why we need to apply Dijkstra to find the shortest path when we find the shortest path using BFS traversal.

[@RamKumar-kz8gg]

following

[@striver_79]

BFS will take longer since it does not follows the greedy method of choosing the shorter path, so you will end up pushing any node a number of times into the queue actually.. which will end up taking a lot of time, over here, you always start with the shortest node reachable and then try to move ahead..

[@darkamv-x5822]

You are best

[@pawanlok1776]

thank you for making this video ,

[@techcode356]

Thank You!

[@bhaveshkumar6842]

Thank you, Striver!!!!!!!!!!

[@sarthaksinghrajput5462]

Thank you Bhaiya!

[@nileshsinha7869]

Great explanation (as always)👌🙌

[@mayankkumar4864]

bhaiya, can you please explain that, why didn't you return the value of "low" or "high" from the function double getNthRoot , as it will be the value of the root ?

[@CodePinaka]

understood

[@ayushbisht2689]

Best explanation.

[@funenjoynilaypatel4553]

9 march 2022 9:39 pm

[@aandz6194]

Im little confused because..... Either we get the root of the number don't we check until 10^(-6)....... So what will be time complexity now in the worst case.....?

[@lakshmiprasanna7058]

Understood 💯💯💯

[@jotaroackerman3447]

amazing video bhaiya

[@s_3095]

thanks bhai striver

[@shubhambhardwaj8894]

Thanks

[@shubhamnalawade1606]

Outstanding explanation

[@shubhamnalawade1606]

Could you please make videos solving coding problems in contests

[@son_of_a_dentist8107]

very good video

[@antrapurohit8010]

great solution. but it is not accepted in coding ninja platform

[@AbhishekKumar-td5zu]

tqsm bhaiya

[@radharamamohanakunnattur3035]

Understtood!! and a Big Thanks!!

[@dhruvmittal4992]

why the search space is not 1 to 13 in first example ?

[@abcsumits]

what about interpolation search?

[@yashwagh83]

Thanks for your efforts and sleepless nights. You are doing god's work Raj.

[@ankitkholiya4305]

Thanks bro you are great

[@srujanat483]

Understood

[@tejaswi4650]

How did you decide we need to stop at 1e - 6?

[@prakharagarwal6237]

it will be given in the question itself

[@shivansh8006]

Why we can not use this " return pow(2, log2(m) / n); ". It will give the same answer :/

[@shivansh8006]

Bhai ye btado yar koi, iski time complexity kam hai na compare to the solution given in the video??

[@sonushaw3715]

Thank you bhaia love you❤

[@prateekverma9166]

Can anybody tell why we haven`t used low=mid+1 or high=mid-1

[@takeUforward]

Because we want annswer in terms of decimal places, doing a -1 will not help :)

[@prateekverma9166]

@@takeUforward Got it ,thanks Striver

[@Sksahu_123]

Bhaiya jisme setprecision use karte so wale bhi question upload kardo

[@kushalchakraborty8615]

Great content

[@umarqureshi8499]

so good bhai!!!!!!!!!

[@ahishnar1568]

Really nice explanation striver.

[@takeUforward]

Pura th dekh lo 😂

[@ishankbansal9239]

@@takeUforward 🤣🤣🤣🤣🤣🤣🤣🤣

[@ahishnar1568]

@@takeUforward Pehle se pata hai sir Awesome hi hone wali hai. I am your current batch student. That is why I know. 😅☺️🤘

[@Steve-kv5we]

Understood💯💯

[@thrilokponnuru3131]

Why the search space start from 1? What happens when m value is negative

[@shubhamrana1776]

Sir in the constraints N=300 and since we are searching in 1 to m , Why the value x ^300 not overflowing while calculating the power? Please help

[@amitkumaryadav7240]

Can anyone explain why time complexity is not n×log(m)

[@AnkitMishra-mz4xt]

Eagerly wanting

[@codeguy21]

@striver , please use this channel also to i.e in english about how u do in your hindi channel ! that would be great for non hindi speakers ! thanks

[@shubhamsinha2362]

Why can't we just use the Pow function?

[@ayushkapri9082]

why search space is not reduced to mid - 1, why just mid ??

[@takeUforward]

Because mid could be your answer..

[@SatyamKumar-bw4vi]

Hare Krishna !🙂

[@bilalkhan2298]

Can't thank u enough

[@Tommyshelby602]

low = 0 to pass 11th tc on coding ninja

[@ng3w462]

Can I achieve command on full DSA in 6 months?

[@RamKumar-kz8gg]

you can do whatever you can imagine

[@ng3w462]

@@RamKumar-kz8gg thanks for the motivation bro...🤟

[@JackkofAll]

Raj bhaiya is there a discussion group for your channel on telegram ? If not please create one , it would be great to discuss stuff among all of us

[@takeUforward]

link me h na

[@VishalKumar-xm5ue]

I have a doubt given this question: 1st in technical round : If the company wants a "coder" then y cant we use "pow" function 2nd in interview round: If the interviewer asks and we write him 2 lines code of using same "pow" will he be like no i want some other technique?(I assume they will ask....because i havent faced too many interviews yet...

[@bhupeshbhatt4849]

Can anyone explain why we have set low = mid and high = mid and not low = mid +1 and high =mid -1

[@VivekKumar-zo7kr]

lets suppose from striver explanation, mid was 14. so he not moved to mid-1 which is 13 because 13.1 to 13.9 might also be a possible answer. in the same way, lets suppose mid was 3 and if we had moved to mid-1 i.e. 2, then we will not be able to access 2.1 to 2.9 which might be an answer..

[@pk4288]

@@VivekKumar-zo7kr Thanks for this explanation.. I was not able to get this part :)

[@namanchandak1532]

My this code require less no of calculations because whenever I found the number I am going to return it And in your code if 'l' pointer is on the ans then your *r* first approach to the pointer then it will leave the while loop and again calculate the ans then it will return int NthRoot(int n, int m) { // Write your code here. int l=1,r=m; while(l

[@shivamgupta-fm8qs]

US