BS-11. Find the Nth root of an Integer

Рет қаралды 141,362

take U forward

Күн бұрын

Пікірлер: 246

@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

@bharatmehta30 Жыл бұрын

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

@dank7044 Жыл бұрын

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

@cinime Жыл бұрын

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

@harshmagarwal3196 7 ай бұрын

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

@VarshaSingh-hi2sb 4 ай бұрын

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 4 ай бұрын

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

@rishabhgupta1222 4 ай бұрын

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

@HardikDoshi-ml8ii 7 ай бұрын

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

@Bigg_boss_trolls Ай бұрын

our teaching style is awesome

@AtulKumar-c4x7l Жыл бұрын

understood Thank you striver for such an amazing explanation.

@johndurai2226 Жыл бұрын

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

@hareshnayak7302 9 ай бұрын

Understood,Thanks striver for this amazing video.

@manavsingh5919 Жыл бұрын

Thank you Striver....Understood everything🙂

@omkarsawant9267 10 ай бұрын

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.

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

@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 10 ай бұрын

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

@suryanshsoni3420 10 ай бұрын

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

@kunalsingh8796 Жыл бұрын

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

@DivyamGupta-ly4ds Жыл бұрын

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

@NitinKumar-wm2dg Жыл бұрын

understood bhaiya, thank you for this tutorial

@creepitup 13 күн бұрын

here if you dont understand sir solution : int NthRoot(int n, int m) { // Write your code here. int low=1;int high=m; while(lowm){ high=mid-1; } else low=mid+1; } return -1; }

@priyanshuchoudhary246 Жыл бұрын

Amazing Playlists

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

@AnmolGupta-oj4lm Жыл бұрын

Understood Very Well!

@venkateshcharyakaram6547 3 ай бұрын

explaining the concepts excellent

@zebra-er6xc Жыл бұрын

at 2:57 time complexity will be O( Nth Root (M)) right?

@dhruvchopra26 Жыл бұрын

Yes he has corrected it in the video also

@purushottam108 7 ай бұрын

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

@justcodeitbro1312 Жыл бұрын

Damn bhai what a great explanation thanks alot

@savitore 9 ай бұрын

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?

@yashaggarwal6013 10 ай бұрын

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

@RAHULMAHESHWARIdexter 7 ай бұрын

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)

@karthik-varma-1579 4 ай бұрын

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

@captainakash8914 8 ай бұрын

thanks you striver for.... easy explanation

@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

@shaswatshah4920 7 ай бұрын

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

@shoaibaltaf1128 4 ай бұрын

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

@graviton001 5 ай бұрын

Solved this too myself thnx ❤

@KarthikNandam-xs4qn 2 ай бұрын

understood my g 🔥

@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

@ashutoshranjan4644 Жыл бұрын

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

@TrinmoyDutta 9 ай бұрын

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

@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

@YourCodeVerse Жыл бұрын

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

@srilathareddy9450 9 ай бұрын

wow explanation

@harshilkaria7420 3 ай бұрын

Can anyone please clear my doubt what if in if() condtion in while loop I directly calculate power of mid like this if(pow(mid,n)==m) will this genrate overflow ?

@lakshmiprasanna7058 Жыл бұрын

Understood 💯💯💯

@VivekSharma-sk3vp 9 ай бұрын

understood!! nicely

@puzzledbird9650 Ай бұрын

another approach with same concept int nthRoot(int n, int m) { int low = 1; int high = m; int ans = 1; while (high >= low) { int mid = (high + low) / 2; if(pow(mid, n) == m) return mid; if (pow(mid, n) > m) { high = mid - 1; } else { low = mid + 1; } } return -1; }

@puzzledbird9650 Ай бұрын

successfully passed all the test cases...

@damnrish4873 Ай бұрын

@@puzzledbird9650 not sure how? this should have been overflowed "if (pow(mid, n) > m) ".

@akshatsamdani Жыл бұрын

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

@SYCOA12CHAITANYAASOLE 7 ай бұрын

Understood !! 😎😎

@CodewithKing360 5 ай бұрын

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 5 ай бұрын

Not some, only 1 iteration

@THIRUORUVAMMEY Ай бұрын

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

@NazeerBashaShaik 9 ай бұрын

Understood, thank you.

@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

@senseiAree Жыл бұрын

Understood ❤

@viveksoni6823 10 ай бұрын

why can't i keep like for(int i = 1; i m) return 0; res = res*mid; // if(res > m) return 0; } It's giving wrong answer.

@HimanshuYadav-ry8tk 10 ай бұрын

if mid=5 and m = 34 then it will go like this first iteration -> res(1)>m not true, res=1*5 second iteration -> res(5)>m not true, res=5*5 third iteration ->res(25)>m not true, res=5*5*5 so your if is not working correctly

@viveksoni6823 10 ай бұрын

@@HimanshuYadav-ry8tk thanks a lot

@sanjanaadepu6012 2 күн бұрын

Understoooood!

@theundisput3d 11 күн бұрын

thank u so much striver

@sahadevnai8040 5 ай бұрын

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

@harshilpatel3205 4 ай бұрын

Understood 🙏🏻

@mangeshtale2818 3 ай бұрын

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

@Durt_kiloz.9643 Ай бұрын

Why cannot we take high as m / 2 as it takes less no. Of checks

@sushyyyyyyyy 7 күн бұрын

take example n = 1, m = 10, if u do m/2, then you won't be able to get 10 which is answer...so here its not possible

@harsh_parmar601 10 ай бұрын

Understood 🎉

@shashankadiga7796 Жыл бұрын

does anyone know where to use low

@oyeshxrme 5 ай бұрын

understood bhaiya

@music-loverFam 5 ай бұрын

Understood😊

@modiji8706 Жыл бұрын

able to write this code myself

@diponchetia9381 8 ай бұрын

understood clearly

@KeepCoding69 3 ай бұрын

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

@RaunitJaiswal-s9v 3 ай бұрын

Last for today 😮

@gopimalisetti7900 Жыл бұрын

Understood! 😀

@chiragbansod8252 10 ай бұрын

UNDERSTOOD

@sharubs9907 Жыл бұрын

What is square root of -6

@Learnprogramming-q7f 11 ай бұрын

Thank you Bhaiya

@shaiksoofi3741 10 ай бұрын

understood Thank you

@AbhishekBhattacharjee-j2m Жыл бұрын

UNDERSTOOD

@priyaanshusoni 8 ай бұрын

why're we returning 2 ?

@dreamyme543 Жыл бұрын

understood🙃

@thatsathishkumar Жыл бұрын

Nice bhai

@dipanshuraj7868 8 ай бұрын

instead of using another function, we have to use the pow(mid, n) function. #include int NthRoot(int n, int m) { // Write your code here. for(int i = 1;i m){ return -1; } } return -1; }

@navinvenkat3404 6 ай бұрын

int NthRoot(int n, int m) { if (m == 0) { return 0; // Special case: 0th root of 0 is 0 } int low = 1; int high = m; int result = -1; while (low m) { high = mid - 1; } else { low = mid + 1; result = mid; // Keep track of potential result } } return result; // Return the last valid result found } whats wrong with code ?