BS-11. Find the Nth root of an Integer

[@andrewbeef8758]

this is a hidden gem playlist in entire youtube

[@nehathakur40]

The most simplified explanation one could ever get!

[@HarshKumar-ip5nr]

The edge case of overflow was amazing. Thank you for such amazing content. Consider completing the series we are eagerly waiting.

[@mrsttechno5974]

Your teaching style is awesome, I understand everything in detail

[@joeljacob4685]

Handling the overflow case was amazing !! I didn't got that one

[@Bigg_boss_trolls]

our teaching style is awesome

[@bharatmehta30]

Was missing the overflow case. Thanks to this amazing video.

[@harshmagarwal3196]

Sometimes I feel he is scolding me. But honestly this is one of the best playlist available on YT.

[@VarshaSingh-hi2sb]

What will be the time complexity ? will it be nlogm where m is the number whose root needs to be calculated and it the given power? log m for BS and multiply it with n foe calculate power of every number am I right ?

[@mahidhruv7]

@@VarshaSingh-hi2sb Yes correct, complexity will be O(n log (m))

[@rishabhgupta1222]

@@VarshaSingh-hi2sb it feels lyk u are scolding 😅

[@KrishnaKumar-b4m9p]

@@VarshaSingh-hi2sb for calculating power there are 2 approaches with time complexity O(n) and O ( log n). so your overall time complexity will depend on which method u choose. where as for the binary search part time complexity will be O (log m)

[@dank7044]

suppose M=10^63-1;( max value of long long), and mid=10^63/2, now is mid

[@girikgarg8]

Done, Here's my approach to this question: long long binPower(int a,int b,int m){ long long ans=1; long long temp=a; while (b){ if (temp>m || ans*temp>m) return INT_MAX; // so that high moves to mid-1 if (b&1){ ans=1LL*ans*temp; } temp=1LL*temp*temp; b>>=1; } return ans; } int NthRoot(int n, int m) { int low=1; int high=m; int ans=0; while (lowm) high=mid-1; else low=mid+1; } return -1; }

[@cinime]

Understood! Super amazing explanation as always, thank you so so much for your effort!!

[@suryanshsoni3420]

long start = 1; long end = m; while (start m / (Math.pow(mid, n - 1))) { end = mid - 1; } else if (mid < m / (Math.pow(mid, n - 1))) { start = mid + 1; } else { return (int) mid; } } return -1; This also works.

[@yashaggarwal6013]

what is the logic behind m / (Math.pow(mid, n - 1) ?

[@suryanshsoni3420]

@@yashaggarwal6013 mid * mid**(n-1) = mid**n

[@omkarsawant9267]

Edge case explained when mid^n > m then overfllow occurs int func(int mid, int n, int m) { long long ans = 1; for (int i = 1; i m) { return 2; } } if (ans == m) { return 1; } // return 1 if ans == m return 0; // return 0 if ans < m } For example, let's say mid = 3, n = 2, and m = 8. During the loop, the value of ans will be calculated as follows: ans = 1 * 3 = 3 (after the first iteration) ans = 3 * 3 = 9 (after the second iteration) At this point, ans (which is now 9) is greater than m (which is 8), and the function will return 2, indicating that 3^2 is greater than 8.

[@AtulKumar-c4x7l]

understood Thank you striver for such an amazing explanation.

[@KeepCoding69]

It's better to keep high as m/n. We can reduce the number of checks using this.

[@AayushRana-kl4lj]

Root of any even num is always even and same goes with odd too. We should apply this concept too to reduce a bit of time complicity.

[@manavsingh5919]

Thank you Striver....Understood everything🙂

[@hareshnayak7302]

Understood,Thanks striver for this amazing video.

[@johndurai2226]

I am your big fan because of your videos are well and explanation also

[@NitinKumar-wm2dg]

understood bhaiya, thank you for this tutorial

[@venkateshcharyakaram6547]

explaining the concepts excellent

[@AnmolGupta-oj4lm]

Understood Very Well!

[@priyanshuchoudhary246]

Amazing Playlists

[@kunalsingh8796]

consistency to gave such awesome videos makes u a good youtuber ...keep doing sir

[@DivyamGupta-ly4ds]

oh i really see that coming....😂😂

[@purushottam108]

to understand this video i lean power exp it take me 2 hrs to learn because of -ve power in leet code ,and at last striver solve this porblem by simple for loop.🤩🤩🤩🤩🤩🤩❤❤😥😥

[@KrishnaKumar-b4m9p]

dont worry that will also be useful. it was asked in meta coding interview to implement pow(x,n) function using log n time complexity

[@shoaibaltaf1128]

int NthRoot(int n, int m) { int low=1; int high=m; int mid; while(lowm)high=mid-1; else low=mid+1; } return -1; } this code got submitted at once without any overflow

[@srilathareddy9450]

wow explanation

[@karthik-varma-1579]

public class Solution { public static int NthRoot(int n, int m) { int ans = -1; int low = 1; int high = m; while(low m){ high = mid - 1; } else{ low = mid + 1; } } return ans; } }

[@HardikDoshi-ml8ii]

can we use power func --- pow(mid,n) ??? instead of writing different function??

[@THIRUORUVAMMEY]

int ans = 0; for(int i=1;i

[@captainakash8914]

thanks you striver for.... easy explanation

[@oyeesharme]

understood bhaiya

[@graviton001]

Solved this too myself thnx ❤

[@ashutoshranjan4644]

In python, it doesn't cause any issue with that code. But thanks for that edge case of c++.

[@KarthikNandam-xs4qn]

understood my g 🔥

[@harshilpatel3205]

Understood 🙏🏻

[@codeman3828]

Understood.

[@justcodeitbro1312]

Damn bhai what a great explanation thanks alot

[@TrinmoyDutta]

lets assume we need to find nth root of num, so if we set low=0, high=num/n, then the overflowing edge case can be avoided to some extent, as we know nth root cannot exceed num/n...

[@DeadPoolx1712]

UNDERSTOOD;

[@music-loverFam]

Understood😊

[@VivekSharma-sk3vp]

understood!! nicely

[@diponchetia9381]

understood clearly

[@nowornever8552]

Understoood

[@NazeerBashaShaik]

Understood, thank you.

[@Learnprogramming-q7f]

Thank you Bhaiya

[@chiragbansod8252]

UNDERSTOOD

[@YourCodeVerse]

Understood✅🔥🔥

[@senseiAree]

Understood ❤

[@sarangkumarsingh7901]

Understood...............

[@savitore]

when you are modifying code for overflow, the T.C got changed to O(n*logm). How to do it in O(logn logm)?

[@mcbotface]

Can you share the code where you modify exponentiation function to handle overflow situation instead of naive multiplication function?

[@SYCOA12CHAITANYAASOLE]

Understood !! 😎😎

[@harsh_parmar601]

Understood 🎉

[@lakshmiprasanna7058]

Understood 💯💯💯

[@meenakshitewary7015]

God explantion

[@yashaggarwal6013]

Why can't we use pow(mid,n) to calculate power instead of writing an entire function in C++?

[@RAHULMAHESHWARIdexter]

watch the video from 15:30 till end, it will cause overflow. one workaround is to do pow(mid,1/n), take floor of it and check if it is same as the number (i mean to say if its a integer instead of some float value like 3.21 something)

[@modiji8706]

able to write this code myself

[@shaiksoofi3741]

understood Thank you

[@padmavatishah9922]

Understood sir

[@dreamyme543]

understood🙃

[@shubhamkumar170]

Understood!

[@rushithagudipudi7742]

Understand

[@AbhishekBhattacharjee-j2m]

UNDERSTOOD

[@thatsathishkumar]

Nice bhai

[@CodewithKing360]

bhaiyya in square root question we can minimize some iteration using high=n/2 a squreRoot of number always lies in 1 to num/2😄

[@afrazurrahmantial6805]

Not some, only 1 iteration

[@AmanKumar-qz4jz]

thanks

[@ayushirastogi9725]

yep understood!!

[@drizzle01]

understood

[@ShubhanshuG007]

Understood

[@AtulKumar-c4x7l]

Striver can u please explain how can I do with binary exponentiation.....i tried still i am not able to figure it out.... i used following code: long long ans=1; while(n>0) { if(n%2==1) { ans=ans*mid n=n-1; } else{ mid=mid*mid; if(mid>m) return 2; n=n/2; } } if(ans==m) return 1; return 0;

[@rishabhagarwal6057]

This is using binary exponentiation. TC = O(log(m)*log(n) class Solution{ public: long long fun(long x, long long n, long long m){ long long ans =1; while(n>0){ if(n%2==1){ ans=ans*x; if(ans>m) return -1; n--; } else{ x=x*x; if(x>m) return -1; n/=2; } } } int NthRoot(int n, int m) { long long low =0; long long high =m; while(low

[@MohitKumar-o3l1u]

Understood!!

[@humanity7880]

understood!

[@rupalikumari8829]

Understood:)

[@amitranjeetjha1240]

Understood

[@shaswatshah4920]

Can't we use mid**n to check and then increase or decrease the low and high accordingly. this way we don't have to use the function and no need of for loop also

[@gopimalisetti7900]

Understood! 😀

[@utsavseth6573]

Lovely.

[@random_akki]

instead of func can we use pow(mid,n)??

[@Sankhamit]

no at the end of the video bhaiya explained the case of 10 to the power 90 which will overflow so we use the function , if we use pow it will directly give 10 the power 90 which will overflow and we ll not get output

[@random_akki]

@@Sankhamit leetcode accepted the solution using pow

[@Raj10185]

my implementation :- typedef long long ll; ll multiply(ll mid , int n,int m) { ll ans=1; for(int i=1;im) { //to overcome the overflow bada ho gya to bas break kar do break; } } return ans; } int NthRoot(int n, int m) { if(n==1) return m; int low = 1; int high = 1e5; while(low

[@ArpanChakraborty-do6yz]

just op❤‍🔥💯

[@raghavkansal3765]

"understood"

[@sahadevnai8040]

public class Solution { public static int NthRoot(int n, int m) { int low = 1; int high = m; while (low m) break; } if (val == m) { return mid; } else if (val > m) { high = mid - 1; } else { low = mid + 1; } } return -1; } }

[@shashwat_harsh]

understood.

[@RaunitJaiswal-s9v]

Last for today 😮

[@akashkumaryadav1827]

🔥

[@DevanshiKapla]

instead of the check func can we use inbuilt power func that will also work

[@takeUforward]

Overflow case will be an issue

[@DevanshiKapla]

@@takeUforward Okay bhaiya

[@kushagramishra5638]

UnderStood!

[@suryasaimaheswar8636]

understood:)

[@esmamanyt7048]

i have a doubt this just failing the test case but not giving any error and if it not giving an error how can we suppose to find out the problem there has to be any trick or tips for this type of edge case

[@prthms_]

i got it

[@MischievousSoul]

Cfbr

[@googleit2490]

Understood :)

[@dayashankarlakhotia4943]

Understood please solve some hard problems

[@mangeshtale2818]

int NthRoot(int n, int m) { // Code here. int low=1; int high =m; while(low m){ high = mid-1; }else{ low = mid+1; } } return -1; } T.C = O(logm * logn) logm (for binary search) and logn(for calculations of power) so isn't this better??

[@Manishgupta200]

Dealing with the overflow case is too tricky. That's kind of thing is taughts you only

[@akshatsamdani]

Isnt the time complexity for this code is O(nlogm)

[@suyashmishra6946]

Understood!

[@raghavkansal3765]

what is return 1 return 0 and return 2 i didnt get that

[@yesaryann]

@@raghavkansal3765 same bhai

[@anubhav_gupta_]

US✅

[@anshsaxena7297]

UnderStood