thanks brother, i was also thinking of the same issue but since there were no errors in the testcases so i ignored it. they can bring up this issue in an interview
Correction at time 12:45 the time complexity of the brute force solution is not O(n) as suggested by striver but it is O(sqrt n) according to me as the loop will break after that condition always And plz striver bhaiya vidios jaldi jaldi daal do bhot wait kar liya
@@champion5946 chal na lavde aa thuu maine mana kiya kya ki wo efforts nahi maar raha striver ke liye 1000 percent izzat hai mere dil me and mere msg ka wo matlab nahi tha
first naive approach had TC of O(sqrt(n)) but binary search has TC of O(log(n)) which is eventually slightly better than former one for very large values.
Understood; but to be noted we can also take low = 1 and high = n/2 this also works because sqrt of a number is always less than or equal to n/2. But I guess here it do not matter as this will only reduce one iteration but if we are dealing with a program which regularly calculate the sqrt these one one iteration which is reduded might sum up and save a lot of time..[ just a random thought]
Hi Raj, I think the solution can be bit more efficient with the TC of O(log n/2) instead of O(log n). Since, we know square root of any number n can't be bigger than half of that number i.e, n/2 therefore we would take high as n/2 instead of n. Here's the code: class Solution { public int mySqrt(int x) { if(x == 1) return 1; int low = 1, high = x/2; int result = 0; while(low
using the concept of lower bound : private static int getSquareRoot(int n) { int low = 1; int high = n; while (low(long)(n)){ high =(int) mid-1; } else { low =(int) mid +1 ; } } return low-1; }
dada, cant we optimize it further by reducing the search space. we can keep high as n//2 initially cause a square root of a number can never be greater than half of the number.
If you observe then we don't really have to take high = n Because in all the cases we are only going till half of n.... Sooooo I think we can further reduce our search space 1 to n/2 and then apply binary search 👨💻
Right. Although even if you start with n, the first partition will end up dividing it into half. So should not make a huge difference. Also if you are considering n/2, we need to make sure we are not rounding down values like 1.
bhaiya please ek series bitmasking pe bhi bna dena. I know you already are busy.But jab ye playlist khatam ho jaye aur time mile then plese consider. If you have any recordings/ suggestions on how to learn toh please ek bar bta dena 😞😞😞
Hey!, can anyone tell , why this code is not working in one of the test cases of coding ninjas,(actually , i am unable to find that test cases on coding ninjas), but it is passing all test cases on gfg, if anyone can figure out?
The check "mid * mid
Thanks bro😊
@@anigaming7146 welcome
thanks brother, i was also thinking of the same issue but since there were no errors in the testcases so i ignored it. they can bring up this issue in an interview
@@pushankarmakar1783 all the best
Thanks for help.❤❤
Had been desperately waiting for the series to restart. Thanks a lot.
You can also take high as n/2 rather than n intially as it is certain that ans will lie in a range of 1 to n/2
Yes
i did the same initially
for 1 all write differently ri8>\]
int mySqrt(int n) {
if(n==0)return 0;if(n==1)return 1;
int ans=-1;
int start=1;int end=n/2;
while(start
Understood!!
Here are the time stamps:
00:00 - 00:15 Intro
00:16 - 1:15 -Problem description
1:16 - 4:00 - Brute(linear)
4:01-5:20 - Binary search intuition
5:20 - 16:16 - Optimal solution
16:17 - 16:45- code
16:45 - 17:10 - outro
Why bro? just why ??
@@Shanky_17 Just love him for that
I solved this question without watching the video!!!
OMG!!!
STRIVER YOU BEAUTY!!!!!!!!!!!!!!!
Correction at time 12:45 the time complexity of the brute force solution is not O(n) as suggested by striver but it is O(sqrt n) according to me as the loop will break after that condition always
And plz striver bhaiya vidios jaldi jaldi daal do bhot wait kar liya
thodi sharam kr... wo banda full time job me itna kr rha h... patience nhi h logo ko free ki chizz bhi jalid chaiye
@@champion5946 chal na lavde aa thuu maine mana kiya kya ki wo efforts nahi maar raha striver ke liye 1000 percent izzat hai mere dil me and mere msg ka wo matlab nahi tha
@@champion5946are didi placement hai next month se isliye thoda patience nhi rakh paa rhe log
Always top level concept clearer ❤
Hats Off to the content and it's creator ! Understood each and every part of the video.
Excellent explanation ❣.. Waiting for linked list series💛💛
first naive approach had TC of O(sqrt(n)) but binary search has TC of O(log(n)) which is eventually slightly better than former one for very large values.
Good to see from brute force approach to optimal approach.
I aam doing dsa from tha last 6 months and i found u yesterday and now i am a fannnn...
hows your dsa prep going now , i just started , does it get any better?🤣
Understood; but to be noted we can also take low = 1 and high = n/2 this also works because sqrt of a number is always less than or equal to n/2. But I guess here it do not matter as this will only reduce one iteration but if we are dealing with a program which regularly calculate the sqrt these one one iteration which is reduded might sum up and save a lot of time..[ just a random thought]
What about 2?
@@abhimanyushekhawat2626 Works for 2 as well.
just right an if condition at the start @@abhimanyushekhawat2626
@@abhimanyushekhawat2626 for n=2 the answer is 1, if you carefully observe low = 1 high = 1 and mid is also 1*1
Your explanation is just awesome.
Respect to Striver ❤ for such a easy explanation
Hi Raj,
I think the solution can be bit more efficient with the TC of O(log n/2) instead of O(log n). Since, we know square root of any number n can't be bigger than half of that number i.e, n/2 therefore we would take high as n/2 instead of n. Here's the code:
class Solution {
public int mySqrt(int x) {
if(x == 1)
return 1;
int low = 1, high = x/2;
int result = 0;
while(low
@@impalash_ag good observation
yup i also thought of that
@@himanshukamble765 what about n=2 ?
@@higgsboson67 for n=2 the answer is 1, if you carefully observe low = 1 high = 1 and mid is also 1*1
amazing explanation striver, understood.
we can check sqrt from 1(low) to n/2 (high) as well
using the concept of lower bound :
private static int getSquareRoot(int n) {
int low = 1;
int high = n;
while (low(long)(n)){
high =(int) mid-1;
}
else {
low =(int) mid +1 ;
}
}
return low-1;
}
Wow that was a very slick approach, good job.
use the check value as if( mid
this is somewhat similar to Newton-Raphson method we use in engineering mathematics.
thanks bhaiya for your endless efforts
dada, cant we optimize it further by reducing the search space. we can keep high as n//2 initially cause a square root of a number can never be greater than half of the number.
understood..
Thank you striver for such an amazing explanation
Understood! Awesome explanation as always, thank you very very much for your effort!!
Thank you Striver...Understood everything🙂
If you observe then we don't really have to take high = n
Because in all the cases we are only going till half of n.... Sooooo
I think we can further reduce our search space 1 to n/2 and then apply binary search 👨💻
Right. Although even if you start with n, the first partition will end up dividing it into half. So should not make a huge difference. Also if you are considering n/2, we need to make sure we are not rounding down values like 1.
Thank you for creating such courses
Understood 🤘
understood clearly...thanks a lot, u have given me hope!
Great video you made thank you very much sir waiting for the linked list Video.
Binary Search on answers finally !
Striver Bhaiya please august end tak a to z sheet complete kra do
10:50 Opposite Polarity
Lec 12, 13 also has
if we take high as n/2, then also we will get a desirable ans!
US bhaiya
In pseudo code it was mentioned either we can return ans or high, but returning ans giving error
Was able to do it myself thnx ❤
Started 2 video karke sojaynege bhaya 😮😮
Largest integer or smallest integer are correct terminologies.
You are awesome brother
Understood, Thanks striver for this amazing video.
Just awesome explanation.
Understood RAJ.
Thanks a lot Bhaiya
Superb explanation
awesome explanation sir
❤Awesome as usual
Bhaiya why can't we use high as n/2 instead of n at start in the function(instead of 28 we can use 14 ) 13:14
Understood Bhaiya
Thank youuu striver❤
Understood Very Well!
Understood striver!!
Worth content 👍
27 July 2024 Saturday
10:42 PM
done ✅
STRIVERS TIP = if one part of a vector / data strc can be fully eliminated from consideration then binary search can be used
What if we have to find exact ans not an integer?
checking if the (mid*mid==x) and returning mid before the actual "check" makes the code more efficient . am i right?
Understood✅🔥🔥
UNDERSTOOD;
Understood
😇
can someone explain how is linear O(N) ?? It will always be O(sqrt(N)) only right ?? Because for 28 we at max take 6 iterations.
you r incredible !!!!!!!!!!
Understood!!! Thank You
UNDERSTOOD
Understood !! 😎😎
Understood.......
Can you come up with a video where we need to find square root upto decimal precision p
Understood, thank you.
understood!
great video!❣
UNDERSTOOD
Superb
Legendary boss
bhaiya please ek series bitmasking pe bhi bna dena. I know you already are busy.But jab ye playlist khatam ho jaye aur time mile then plese consider. If you have any recordings/ suggestions on how to learn toh please ek bar bta dena 😞😞😞
underatood
waiting for linked list, bit manipulation and strings please
Thank you very much
Understood ❤
❤❤great video bro
great video
Understood
The demand of Levis Tshirt increses from Tomorrow
Hey!, can anyone tell , why this code is not working in one of the test cases of coding ninjas,(actually , i am unable to find that test cases on coding ninjas), but it is passing all test cases on gfg, if anyone can figure out?
Check the data type..mine was also not wokring but then I changed the data types to long long , it passed all the test cases
mine was failing for n = 1, as I had my upper bound at n/2 which was rounding it down to 0.
@@Simran-ns8gp i also changed but it is not working pls tell
Understood!
Understand
Bhaiya plz start linked list series
Thanks you a lot,
Can't thank enough
Understood bhayaaaaaaaa
Understood🙃
understood
understood
Bhi logic kayse build Karu kuch batao plzzzz
Understood boss^^
Understood
understood!
Great
understood!!
thank u sir