Instead of multiplying by running a for loop, we can use Binary Exponentiation technique to do in log N. Video: th-cam.com/video/l0YC3876qxg/w-d-xo.html
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! 💜🙏
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.
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
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 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.....?
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 😎🤩 ....
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
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!!!
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.
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); }
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 ?
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..
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);
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)
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.
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.....?
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...
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..
@@takeUforward if it's upto 2 decimal places, if high = 0.223 and low = 0.222, we should stop the search as difference is 1e-2. Why are we looking upto 1e-3? Please explain
![[FULL EP.16] เซียนพาลุย "เผือก-ฟรอยด์" กรี๊ดลั่น จนปูหนี | เฮ็ดอย่างเซียนหรั่ง | One Playground](http://i.ytimg.com/vi/FsqUvwS3b-Y/mqdefault.jpg)
Instead of multiplying by running a for loop, we can use Binary Exponentiation technique to do in log N. Video: th-cam.com/video/l0YC3876qxg/w-d-xo.html
so sir, should the time complexity be logN*log(M*10^d)??
You shoud not sacrifise your sleep for this.
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.
Fun fact : Scalar is showing their add here also in between the video !
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! 💜🙏
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.
what do you mean by row?
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
We can never thank you enough for such amazing content.
There's nobody like you, Striver. You're the BEST!!!!
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.
Yeah I have mentioned in the pinned comment :)
@@takeUforward yeah just saw that.. Anyways, great content as always.
@@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.....?
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 😎🤩 ....
2:51 LoL
why you take low = mid, why not low= mid+1
and high = mid, why not high = mid-1
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
this is the best explanation of the problem you can find on entire internet . thanks a lot
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
can we use pow instead of multiply function?
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!!!
Always learn new concept . And you makes CP more interesting . I likes your way of explaining time and space complexity. Thanks
Bhaiya your graph series is amazing and those dry runs are awesome thanks bhaiya
enjoy
omg.....4'o clock in the morning....
hats off to ur dedication sir.
Can't thank u enough
this is what I want. an amazing playlist for Binary search.
Bhaiya aap jadugar ho , kya samjhate ho mashallah ❤️❤️
thanks man, u just saved me from failing my class assignment, i've been trying to crack that for 3 days
Best Explanation of Binary Search. Eagerly Waiting for your Tree Series!!!❤❤
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.
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)
But using inbuilt pow function ,it is not passing all test cases
@@akankshamaurya9219 it is working check in gfg practice
Great explanation around intuition building and time complexity. Keep it up bro
You are just doing all the way great, I really thank you for all these wonderful playlists.
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);
}
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
watch love babber video
I have seen a lot on youtube. You are the very best.
Thanks a lot striver. We always learn a new concept through your lecture.
Great Explanation bhaiya
Bhaiya....please make a playlist on the tree as well.
no words, excellent explanation
u r so dedicated man i wanna be also that much
why can't we put an extra condition for multiply(mid,n)==m then return mid?
Because it will take a lot more iteration to become equal to root(M).
@@SudhanshuKumar-lp1nr why? We are not putting the condition inside while loop instead we are putting this as an extra if()
There is no match for your hardwork , but we too would work hard even if it doesn't surpasses yours.
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 ?
Thank you sir understood
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.
following
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..
amazing explaination as always Thanks
Recently asked in Apple Interview to my experienced brother !!!
keep educating bhaiya nicely explained
Great explanation (as always)👌🙌
Great content bhaiya! Learned and understood to the fullest!
thank you for making this video ,
Why the search space start from 1?
What happens when m value is negative
why the search space is not 1 to 13 in first example ?
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);
do you have any question on std platform please provide me for practise
How did you decide we need to stop at 1e - 6?
it will be given in the question itself
hats off to ur dedication 🙏
Thank You!
Why we can not use this " return pow(2, log2(m) / n); ". It will give the same answer :/
Bhai ye btado yar koi, iski time complexity kam hai na compare to the solution given in the video??
Understtood!! and a Big Thanks!!
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)
make these changes cout
@@dipanshusharma9084 why did we do this? as it is asking in the question to check for up to 6 decimal points.
@@muhsinmansooriee_0017 because in the ans it was taking upto 9 decimals , there was mistake in test cases
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.
thank you
what about interpolation search?
great explanation
Can anybody tell why we haven`t used low=mid+1 or high=mid-1
Because we want annswer in terms of decimal places, doing a -1 will not help :)
@@takeUforward Got it ,thanks Striver
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
Understood 💯💯💯
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.....?
😳awesome dada, didn't knew to use binary search this way
Thank you, Striver!!!!!!!!!!
You are best
Thanks bro you are great
Best explanation.
Thank you bhaia love you❤
very good video
@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
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...
amazing video bhaiya
Can anyone explain why time complexity is not n×log(m)
Outstanding explanation
Could you please make videos solving coding problems in contests
Great content
great solution. but it is not accepted in coding ninja platform
thanks bhai striver
understood
why search space is not reduced to mid - 1, why just mid ??
Because mid could be your answer..
Why can't we just use the Pow function?
Thanks for your efforts and sleepless nights. You are doing god's work Raj.
9 march 2022 9:39 pm
Thank you Bhaiya!
tqsm bhaiya
Bhaiya jisme setprecision use karte so wale bhi question upload kardo
Understood
Really nice explanation striver.
Pura th dekh lo 😂
@@takeUforward 🤣🤣🤣🤣🤣🤣🤣🤣
@@takeUforward Pehle se pata hai sir
Awesome hi hone wali hai.
I am your current batch student.
That is why I know. 😅☺️🤘
Understood💯💯
Sde sheet become interesting day by day
code zen pur submit he nhai ho raha
double t=1.000000/n;
double ans=pow(m,t);
return ans;
Can't thank u enough
ay yo mad content G
Big up your thing💯💯
Can I achieve command on full DSA in 6 months?
you can do whatever you can imagine
@@RamKumar-kz8gg thanks for the motivation bro...🤟
Can anyone explain why we have set low = mid and high = mid
and not low = mid +1 and high =mid -1
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..
@@VivekKumar-zo7kr Thanks for this explanation.. I was not able to get this part :)
this solution giving wa in code studio
what can i change in this?
bro did u find any needful?
@@juzarantri864 no I just did pow(m,1.0/n)
Eagerly wanting
so good bhai!!!!!!!!!
Love your effort :)
Where can we pratice more binary search problems ?🙄
If on any platform what keyword do I have to use to get those questions?🙄
Lol use binary search as keyword
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
link me h na
what if i need the ans upto 2 decimal place should the difference will be e^-2?
if possible reply ..
Yeah bro.. -3, so that the first 2 decimal places are correct
@@takeUforward okay..thank you..
@@takeUforward if it's upto 2 decimal places, if high = 0.223 and low = 0.222, we should stop the search as difference is 1e-2. Why are we looking upto 1e-3? Please explain