BS-11. Find the Nth root of an Integer
Вставка
- Опубліковано 20 чер 2023
- Problem Link: bit.ly/3oWhSkW
Notes/C++/Java/Python codes: takeuforward.org/data-structu...
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
this is a hidden gem playlist in entire youtube
The edge case of overflow was amazing. Thank you for such amazing content. Consider completing the series we are eagerly waiting.
The most simplified explanation one could ever get!
Understood! Super amazing explanation as always, thank you so so much for your effort!!
Your teaching style is awesome, I understand everything in detail
Was missing the overflow case. Thanks to this amazing video.
understood
Thank you striver for such an amazing explanation.
Thank you Striver....Understood everything🙂
Handling the overflow case was amazing !! I didn't got that one
I am your big fan because of your videos are well and explanation also
Understood,Thanks striver for this amazing video.
Understood Very Well!
Amazing Playlists
understood bhaiya, thank you for this tutorial
understood!! nicely
Understood, thank you.
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.
thanks you striver for.... easy explanation
Sometimes I feel he is scolding me. But honestly this is one of the best playlist available on YT.
Damn bhai what a great explanation thanks alot
consistency to gave such awesome videos makes u a good youtuber ...keep doing sir
oh i really see that coming....😂😂
Understood 💯💯💯
Understood✅🔥🔥
understood Thank you
yep understood!!
Understood! 😀
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;
}
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.🤩🤩🤩🤩🤩🤩❤❤😥😥
understood clearly
Understood ❤
Understood 🎉
Understood !! 😎😎
Understood❤
understood!
Understood!
Nice bhai
just op❤🔥💯
Can you share the code where you modify exponentiation function to handle overflow situation instead of naive multiplication function?
UNDERSTOOD
Understood!!
Thank you Bhaiya
wow explanation
suppose M=10^63-1;( max value of long long), and mid=10^63/2, now is mid
Understood :)
Lovely.
Understood sir
thanks
Understood
understood
understood.
Understand
understood🙃
can we use power func --- pow(mid,n) ??? instead of writing different function??
Understood...............
In python, it doesn't cause any issue with that code. But thanks for that edge case of c++.
++thanks
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.
what is the logic behind m / (Math.pow(mid, n - 1) ?
@@yashaggarwal6013 mid * mid**(n-1) = mid**n
instead of the check func can we use inbuilt power func that will also work
Overflow case will be an issue
@@takeUforward Okay bhaiya
❤
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
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
Isnt the time complexity for this code is O(nlogm)
when you are modifying code for overflow, the T.C got changed to O(n*logm). How to do it in O(logn logm)?
able to write this code myself
Understood please solve some hard problems
i got it
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.
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;
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
instead of func can we use pow(mid,n)??
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
@@user-hq7yd4wz4y leetcode accepted the solution using pow
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...
does anyone know where to use low
Why can't we use pow(mid,n) to calculate power instead of writing an entire function in C++?
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)
at 2:57 time complexity will be O( Nth Root (M)) right?
Yes he has corrected it in the video also
What is square root of -6
why're we returning 2 ?
UnderStood!
"understood"
i used pow function and overflow didnt happen,why??
Because of weak testcases
1st view❤❤❤❤
Cfbr
US✅
god
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
Dealing with the overflow case is too tricky. That's kind of thing is taughts you only
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.
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
@@HimanshuYadav-ry8tk thanks a lot
First viewer
#include
int NthRoot(int n, int m) {
// Write your code here.
int low = 1, high = m;
while(low
Why 69 as an example 😅?
💀
fantasy no.
US
engineers and their obsession with the number 69😂😂😂😂😂😂😂😂
hahahahahah i was looking for this comment to see wheather someone else has also noticed this or its only me 🤣
1st view
underStood
1st
UNderstood
us
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;
}
Can anyone explain why this code is not working
class Solution{
public:
int power(int i, int n, int m){
long long res = 1;
while(n){
if(n & 1) res = res * i;
if(res > m) return 2;
i = i * i;
n >>= 1;
}
if(res == m) return 1;
return 0;
}
int NthRoot(int n, int m){
int l = 1, h = m;
while(l
kch number na aaye dimag me , 69 jroor ata h 😆
#include
using namespace std;
using ll = long long;
ll binExp(ll a, ll b, ll m){
// implementation of binary exponentiation without modulus
ll ans = 1;
while(b){
if (b % 2 == 1){
if (a 0) ans *= a; // ans may exceed m
else return m+1;
}
a *= a; // a may exceed m
b /= 2;
if (ans > m || ans < 0) return m+1; // may end up negative in case of overflow (not allowed constraints)
}
return ans;
}
int NthRoot(int n, int m) {
if (m == 1) return 1;
int lo = 1; int hi = m;
while(lo m) hi = mi-1;
else lo = mi+1;
}
return -1;
}
The implementation of the binary exponentiation without the help of modulo was one hell of a ride. Thanks for the insight.
Understood ❤