@@codeblooded6760 if 6 is not there in the matrix we wont get 6 as the answer suppose we replace all 6 by 7 then for then we will get >4 but for 6 we will get
Apologies but i did not like the way you explained this , you made it quite complex whereas the algorithm is easy to understand but i thank you for giving us this information.
For so long I avoided this question just because the comments were negative, I finally saw and realised that it's perfect explanation as always ❤❤❤❤❤❤❤
A JAVA Solution with some questions answered whic might confuse some people(me as well). *Q1) Why r and c are always odd?* If r and c both are odd then this means that number of elements int the matrix will also be odd which is actually necessary for binary search to be applicable here(only in this problem, binary serach works for both even and odd elements arrays when the array is linear but not here). Because here we are judging by considering the fact that no of elements less than or equal to current number, which in case of even no of elements can be a number which is not present in the matrix. Having odd number of elements has a property that the middle element is cleary defined (a single mid) so number of elements to the left of it and right of it will be equal but in case of even population we can sometime have a median element which is not present in the array which will not be possible to find in case of a matrix like this without traversing all the elements. This method will give wrong result for even number of elements so let's not worry about it. *Q2 ) Why half = (r * c) / 2 and not (r * c + 1) / 2 as no of elements are odd and we know middle for odd is (n + 1) / 2 ?* To this I will reply that the condition *if (cnt
@Piyush kesari, You are wrong for the "Q1". If case of even number of elements, if you follow this algorithm, you will DEFINITELY get an element from the matrix for sure. BUT THIS IS NOT OBVIOUSLY THE MEDIAN. IF possible show an conuter example to my statement
Thanks for the explanation I had to watch multiple times(2-3). Actually the confusion is that it was not clearly mentioned that we were looking for count(mid)
The search space can be reduced by setting 'high=maxEle(matrix)', and the 'maxEle()' can work in O(noOfRows) as we'll compare the last element only for every row (because the rows are sorted) Thank You sooooo much for such easy explanations!💜
These two points were really helpful!! Second point also proves why low is definitely present in the matrix. We had to find element such that no. of ele
one small condition can be added in for loop to optimize the code by skipping unwanted binary search for each for. We can just check the last element of each row with mid and last element is greater than or equal to mid than we can just add number of columns to cnt Here is the code: for(int i=0;i=matrix[i].back()){ cnt+=m; } else{ cnt+=countSmallerThanEqualTo(matrix[i],mid); } }
yes there is a possibility that our number might not be present the matrix that us why we aree doing mid +1 to check for more numbers and reducing search space in the end we are bound to meet a number which have cnt as
You made time complexity O(nlogn) while doing the loop twice, once outside the equaltomid function and one inside it. The compiler will disregard saying time limit exceeded
The outer loop will run for 32 time at max, the inner loop will always run for N times and the function will run for log(N). So the worst case can go upto 32*N*log(M). It shouldn't give us tle
ANS: Since N*M is always odd we can never get a number that is not in the matrix and still half of the no's are greater than it and half of them is less than that number.
If case of even number of elements, if you follow this algorithm, you will DEFINITELY get an element from the matrix for sure. BUT THIS IS NOT OBVIOUSLY THE MEDIAN.
Why are you taking the high point of binary search as 1e9?? You could have taken the high point as the maximum element of the matrix . In that fashion you could have reduced the search space.
Bro, that's not a good practice tbh...you're just trying to put load for finding the max and min....I know it'll hardly matter but think for very large test cases for example a matrix of size 1e5 * 1e5 , hope you understand
Q::But I am still confused a bit. My Query is, low and high are taken as 1 and 1e9 which are not necessarily in our matrix. And then after we do mid = (low+high)/2, and again we are uncertain whether mid even lies in the matrix or not, and we keep doing it until we come to a favourable situation, and that uncertainty still prevails , but how does this guarantees that whatever 'low' was last calculated actually lies in the matrix??? I mean its just an avg of two numbers! ANS: Since N*M is always odd we can never get a number that is not in the matrix and still half of the no's are greater than it and half of them is less than that number.
This statement can be better understood if you write on paper and check by yourself . m x n = total number of elements . Case 1 : m x n is even E . g [ 1 , 32 , 56 , 67 ] Observation : 34 can be a median but not in array , also 33 , 35 ,36 .... 55 can be median although they are not in array . Case 2: m x n is odd E.g [ 1 , 32 , 56 , 67 , 89 ] Can you tell any number which can be not in array but still can be median ( a number which is greater than half of the elements and smaller than half of elements ) The ans is you can't . There can be only median which is 56 . In order for an element to a median which is not in array it has to be greater than half elements say n1 and other smaller than other half n2 . since n1 and n2 are equal their sum should be even but the array is odd length . It is given than m * n == total elements in array is odd
Median should always be an element from the matrix. How do we assure, lo=mid+1 or hi will be an element from the matrix? As It has possible the middle value is something not present in the matrix .
Please tell me what I am doing wrong? Let us take the test case : [1,2,3,4,5] Let us say initially my low and high are 1 and 7. So mid= 4, I counted number of elements less than equal to 4 as 4. So I see that a median can have this value but let us try to shrink the value, so I move left. New low=1, high= 3, mid=2,smaller equal to- 2 This can't be the median so we move right low=3 hi=4 mid=3 elements less than equal to 3 are 3, which is less so again move right low=4 high=4 med=4 elements less than equal to 4 which are more so we move left low =4, high=3 we break Now median comes out to be 4 but actually it is 3, Please tell my mistake.
But I am still confused a bit. My Query is, low and high are taken as 1 and 1e9 which are not necessarily in our matrix. And then after we do mid = (low+high)/2, and again we are uncertain whether mid even lies in the matrix or not, and we keep doing it until we come to a favourable situation, and that uncertainty still prevails , but how does this guarantees that whatever 'low' was last calculated actually lies in the matrix??? I mean its just an avg of two numbers!
Thats why we keep moving till we dont reach to a number where this breaks.. hence low > high is the break point. When I get confused in this way, I generally take some more examples and a smaller search space and try to do binary search. Only you can increase your understanding by doing self dry runs :) try this method and then ping here if still problem
@@adityaraj5200 Bro ,I also have the same doubt which was raised by you. I tried this algo. on multiple test cases, the ans coming is right but I still can't understand that whatever 'low' was last calculated actually lies in the matrix?
If you have an array and it is sorted , and you have to find median , then the number of elements lesser or equal to median will be equal to number of elements greater or equal to median .. okay ??? so this is the basic intuition to do binary search .. we are dividing the array until there's a breakdown ..we are not searchingg the element here , do you get this ?? *WE ARE NOT SEARCHING , THATS WHY WE WILL DON'T FIND SOMETHING THATS NOT PRESENT ,WE ARE HAVING A BREAKPOINT * get it ? if we come to an elements that is not present and has equal number of elements both the sides , we will trim our array ..and this trimming will lead us to a breakpoint where we will reach our answer.
1*1 = 1 2*2 = 4 3*3 = 9 here for 1 its 1 for 2 its 4 for 3 its 9 and so on. 1-2-3- >> Increasing 1-4-9- >> Increasing Both are linearly increasing. For a bigger number the corresponding result is also bigger then this pattern is monotonically increasing.
can't we go with two functions: cnt1+= countSmallerThan(a[i],mid) cnt2+= countSmallerThanEqualTo(a[i],mid) mid_ind = (n+m)/2 if(mid_ind > cnt1 && mid_ind
because bro, we have to count the numbers less than or equal to itself. For example, in [1, 2, 3, 4, 5], if you find numbers less than 3, you find only 2 numbers. If you consider only less than 3 here, it wouldn't practically give you answer . It would be easy to pick median from the odd number of elements, the question has stated the same that the array has odd number of elements.
can anyone tell me whether the search space be b/w 1 to max-element of the given matrix? Also, what is the intuition behind taking such a large search space?
I have tried using the smaller search space between - min and max of matrix but on gfg it passes some test case while it gives segment ation error on some. I dont know why
it should be vector arr; , don't specify the size because vector arr(row*col) will create vector with '0', and further insertion will take place after it.. i think thats why its not working
I had a doubt , for the sub problem of finding the index just greater than a given value , can we find the last occurrence of that element and then last occurence - 0 will give the elements lesser than and equal to the given value?
@@takeUforward It will take only O(n) time, to find min and max, because 0th and (m-1)th index of row will contain these values, then it will not exceed time
@@takeUforward bhaiya its giving wrong output in gfg plz you try and if its really wrong then pin a comment becoz many of them wasted their whole day in seeing what is wrong in this code like me.
Follow me at Instagram: instagram.com/striver_79/
Join our telegram group: t.me/Competitive_Programming_tuf
Please explain the break point. Why are we returning low? In normal BS we find mid and return mid. What if 6 was not there in the matrix
@@codeblooded6760 if 6 is not there in the matrix we wont get 6 as the answer suppose we replace all 6 by 7 then for then we will get >4 but for 6 we will get
Apologies but i did not like the way you explained this , you made it quite complex whereas the algorithm is easy to understand but i thank you for giving us this information.
so can u explain this in a simpler way?
Bhai sahi me explanation bouncer jaa rha hai ek dum
Totally agreed
th-cam.com/video/Ul8zBtVFXOo/w-d-xo.html watch this and comeback here. you will understand it for sure
very poorly explained couldn't understand anything.
for finding the mid one should use low+(high-low)/2 as when using high+low/2 the high+low can overflow
use 1st one
Okay
we should use start+(end-start)/2
Why not use long long??
For so long I avoided this question just because the comments were negative, I finally saw and realised that it's perfect explanation as always ❤❤❤❤❤❤❤
first time,it's very confusing explanation
true
I second that!
Yup watched it 10+ times but still cant understand
Yes I didn't understand it all
+1
A JAVA Solution with some questions answered whic might confuse some people(me as well).
*Q1) Why r and c are always odd?*
If r and c both are odd then this means that number of elements int the matrix will also be odd which is actually necessary for binary search to be applicable here(only in this problem, binary serach works for both even and odd elements arrays when the array is linear but not here). Because here we are judging by considering the fact that no of elements less than or equal to current number, which in case of even no of elements can be a number which is not present in the matrix. Having odd number of elements has a property that the middle element is cleary defined (a single mid) so number of elements to the left of it and right of it will be equal but in case of even population we can sometime have a median element which is
not present in the array which will not be possible to find in case of a matrix like this without traversing all the elements.
This method will give wrong result for even number of elements so let's not worry about it.
*Q2 ) Why half = (r * c) / 2 and not (r * c + 1) / 2 as no of elements are odd and we know middle for odd is (n + 1) / 2 ?*
To this I will reply that the condition *if (cnt
because this algo works only on odd length array
@Piyush kesari,
You are wrong for the "Q1".
If case of even number of elements, if you follow this algorithm, you will DEFINITELY get an element from the matrix for sure. BUT THIS IS NOT OBVIOUSLY THE MEDIAN.
IF possible show an conuter example to my statement
Thanks for the explanation I had to watch multiple times(2-3). Actually the confusion is that it was not clearly mentioned that we were looking for
count(mid)
Thanks bro
what is mn in your comment?
The search space can be reduced by setting 'high=maxEle(matrix)', and the 'maxEle()' can work in O(noOfRows) as we'll compare the last element only for every row (because the rows are sorted)
Thank You sooooo much for such easy explanations!💜
but in case of 1e9 it runs only for 32 times, still better if no.of rows=500.
@@vishalgupta957 either way order of time complexity would remain the same i.e nlogM
@@sanidhyatahiliani6797 ummm its better if we write M + n logM because there may be a case where say M = 399 , n = 3 => O(399) + O(3*log(399))
What I have figured out after 3 hours is that :
1 ) Why we are taking no of elements
Thanks 😊
These two points were really helpful!! Second point also proves why low is definitely present in the matrix. We had to find element such that no. of ele
thanks
This is not just a video about the problem but also about Binary Search intuition.
If someone comes up with this solution in an interview, hats off to them!
one small condition can be added in for loop to optimize the code by skipping unwanted binary search for each for. We can just check the last element of each row with mid and last element is greater than or equal to mid than we can just add number of columns to cnt
Here is the code:
for(int i=0;i=matrix[i].back()){
cnt+=m;
}
else{
cnt+=countSmallerThanEqualTo(matrix[i],mid);
}
}
One of the hard problm in binary search
Aagya naya video aagya fir placement hi placement hoga
Explanation op!🔥 Thanks a lot striver
I think you made this very complex while teaching. Its very difficult to understand while watching this video
How is "low" always converging to an element within a matrix? This is something I am not able to understand.
Since nai ho rha th right ya left move kr rhe. So ek samay aayega ek banda toh hoga
yes,,, same why is it so that low always converges to answer?
please clarify striver
the video solution is not very clear and it says nothing about the core logic of the solution
I have mentioned this in other comments, do a dry run with other set of examples to understand more..
yes there is a possibility that our number might not be present the matrix that us why we aree doing mid +1 to check for more numbers and reducing search space in the end we are bound to meet a number which have cnt as
You made time complexity O(nlogn) while doing the loop twice, once outside the equaltomid function and one inside it. The compiler will disregard saying time limit exceeded
The outer loop will run for 32 time at max, the inner loop will always run for N times and the function will run for log(N). So the worst case can go upto 32*N*log(M). It shouldn't give us tle
@@sameemsheikh2914 how outer loop will run max 32 times?
@@insane2539 As the INT_MAX here is 2^32, and we are dividing the search space in (log(n) == log(2^32)) times which is 32.
yeah didnt get it
striver
watched it several times, finally understooood bhaiyya!!
Guys low
please bro share the link
really i need that video.
@@_inspireverse___ th-cam.com/video/LcWPKR1uef4/w-d-xo.html
ANS: Since N*M is always odd we can never get a number that is not in the matrix and still half of the no's are greater than it and half of them is less than that number.
I was having this doubt but can you please elaborate this. Thank You.
If case of even number of elements, if you follow this algorithm, you will DEFINITELY get an element from the matrix for sure. BUT THIS IS NOT OBVIOUSLY THE MEDIAN.
just amazing expaination i learn a new concept of takinf a element from the range and solve 2 questions more🤩☺☺☺
Why are you taking the high point of binary search as 1e9?? You could have taken the high point as the maximum element of the matrix . In that fashion you could have reduced the search space.
nice optimization bro and we should take the min as minimum of the matrix
Bro, that's not a good practice tbh...you're just trying to put load for finding the max and min....I know it'll hardly matter but think for very large test cases for example a matrix of size 1e5 * 1e5 , hope you understand
In that case the TC for finding max of a matrix is equivalent to the naive approach and it's better to go with that.
@@adityamahimkar6138 no the TC of finding max is O(rows) bcoz the matrix is sorted row wise
@@pratyushnarain5220 agree since the minimum element would be present in the first column and the maximum element would be present in the last column.
Samajh ni aya par sun kar acha laga😄
This is a very confusing explanation. Please consider replacing this tutorial with a new understandable one
Sheer beauty in explanation!! thankyou so much!!
I believe , you can add another solution using priority_queue (max heap) of size k = (r*c+1)/2.
in qn. they asked for size complexity O(1)
Q::But I am still confused a bit. My Query is, low and high are taken as 1 and 1e9 which are not necessarily in our matrix. And then after we do mid = (low+high)/2, and again we are uncertain whether mid even lies in the matrix or not, and we keep doing it until we come to a favourable situation, and that uncertainty still prevails , but how does this guarantees that whatever 'low' was last calculated actually lies in the matrix???
I mean its just an avg of two numbers!
ANS: Since N*M is always odd we can never get a number that is not in the matrix and still half of the no's are greater than it and half of them is less than that number.
This statement can be better understood if you write on paper and check by yourself .
m x n = total number of elements .
Case 1 : m x n is even
E . g [ 1 , 32 , 56 , 67 ]
Observation : 34 can be a median but not in array , also 33 , 35 ,36 .... 55 can be median although they are not in array .
Case 2: m x n is odd
E.g [ 1 , 32 , 56 , 67 , 89 ]
Can you tell any number which can be not in array but still can be median ( a number which is greater than half of the elements and smaller than half of elements )
The ans is you can't .
There can be only median which is 56 .
In order for an element to a median which is not in array it has to be greater than half elements say n1 and other smaller than other half n2 . since n1 and n2 are equal their sum should be even but the array is odd length .
It is given than m * n == total elements in array is odd
@@realWorldDevStudio What about 33, 34, 66, etc.
@@Anonymous-pj2mv I just gave same examples all the numbers between can be if total elements are even
@@realWorldDevStudio okay, Now I got it. Thanks.
@@realWorldDevStudio but how can we conclude that low is the median?
Thanks for such a great explanation !!
Median should always be an element from the matrix. How do we assure, lo=mid+1 or hi will be an element from the matrix? As It has possible the middle value is something not present in the matrix .
Take some examples, or read other comments. I have answered this..
@@takeUforward use upper_bound function?
Please tell me what I am doing wrong?
Let us take the test case : [1,2,3,4,5]
Let us say initially my low and high are 1 and 7.
So mid= 4, I counted number of elements less than equal to 4 as 4.
So I see that a median can have this value but let us try to shrink the value, so I move left.
New low=1,
high= 3,
mid=2,smaller equal to- 2
This can't be the median so we move right
low=3 hi=4
mid=3
elements less than equal to 3 are 3,
which is less so again move right
low=4 high=4
med=4
elements less than equal to 4 which are more so we move left
low =4, high=3 we break
Now median comes out to be 4 but actually it is 3,
Please tell my mistake.
Use print line to understand..
In the 3rd step you changed the value of high also(from 3 to 4)....
guys if u don't understand at some point look at the code and again watch this video , you will definetly understand :))
I really didn't understand this question to be honest
same, if you knwo can you help me
But I am still confused a bit. My Query is, low and high are taken as 1 and 1e9 which are not necessarily in our matrix. And then after we do mid = (low+high)/2, and again we are uncertain whether mid even lies in the matrix or not, and we keep doing it until we come to a favourable situation, and that uncertainty still prevails , but how does this guarantees that whatever 'low' was last calculated actually lies in the matrix???
I mean its just an avg of two numbers!
Thats why we keep moving till we dont reach to a number where this breaks.. hence low > high is the break point.
When I get confused in this way, I generally take some more examples and a smaller search space and try to do binary search. Only you can increase your understanding by doing self dry runs :) try this method and then ping here if still problem
@@takeUforward Okay thanks. i got it after dry running and observing some random set of testcases of my own .
@@adityaraj5200 Bro ,I also have the same doubt which was raised by you. I tried this algo. on multiple test cases, the ans coming is right but I still can't understand that whatever 'low' was last calculated actually lies in the matrix?
search space can be minimum and max number of the matrix.
@@takeUforward search space can be minimum and max number of the matrix.
Thanks Striver 79 !!!
Great video as always, totally love your voice.
7:28 but isn't that seven numbers excluding eight?????
In this we are not finding the mid by index but by the value ?
Bhai I am like kehna kya chahte ho 🙄..
Really didn't get a bit of it 🥺🥺
U are great explainer on u tube
Very good explanation mind blowing
Explanation is good , but don't take coding ninjas. Its a big waste of money.
Excellent explanation
couldn't understand anything
Thank You So Much Striver Brother......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Bhaiya....plz make a separate playlist on tree
shouldn't the median also be the mean of two middle elements in the case of even numbers?
In the question it was made sure n*m is always odd
Awesome explanation. Thanks for the amazing video.
You confused all of us buddy.
Its confusing for me,
How are we sure that low is present in the matrix?
how can you be sure that low would be a part of the matrix?
If you have an array and it is sorted , and you have to find median , then the number of elements lesser or equal to median will be equal to number of elements greater or equal to median .. okay ??? so this is the basic intuition to do binary search .. we are dividing the array until there's a breakdown ..we are not searchingg the element here , do you get this ?? *WE ARE NOT SEARCHING , THATS WHY WE WILL DON'T FIND SOMETHING THATS NOT PRESENT ,WE ARE HAVING A BREAKPOINT * get it ? if we come to an elements that is not present and has equal number of elements both the sides , we will trim our array ..and this trimming will lead us to a breakpoint where we will reach our answer.
Can the concept used in "Median of Two Sorted Arrays" be leveraged here?
thank you soo much for this kind of video which cleared my concept
nhi aya smjh
krna hi kyu h optimize🙂🤧🤧😭😭😭
Nice explanation your videos are really good...please keep on making such videos.
is not the code a little different from what u explained?
Bhaiya there is one mistake in your code ig ,like you have written if the no of count is
correct
Like other comments,it is very confusing
Thanks you for the wonderful explanation.
what is the answer we get is not there in the matrix
bhai tum bohot acha padhate ho par agar hindi main padhao toh zyada acha , varna kuch samagh nahi aa raha jo tum bol rahe ho.
Same :-(
Why have we taken the search space from 1 and not 0?
Is it mentioned anywhere that 0 will not be the element inside the array?
Yes, in the constraints it is mentioned.
Bhai hgg diya tune is explaination me
low + high >> l ??
what does this mean?
/2 , right shift by 1 means divided by 2^1
Same as low+high/2
10:48 m smgh ni aya bro
Thank you
if (cnt
Understood 💯💯💯
1:56
10:48 m smgh ni aya bro
Same bhai wahan se sab bouncer laga
@@atuldwivedi7677 Same :(
Understood
didn't get
what if 7 was there instead of 6 then 5+1=6 would be wrong ? #Doubt
bhaiyya at 7:31 how come there are 7 nos.
got it😃
Python walo se iss sajjan ko kya taqleef hai bhai😂
Thanks bhai 🙏
What is meant by monotonic increasing?
1*1 = 1
2*2 = 4
3*3 = 9
here for 1 its 1 for 2 its 4 for 3 its 9 and so on.
1-2-3- >> Increasing
1-4-9- >> Increasing
Both are linearly increasing.
For a bigger number the corresponding result is also bigger then this pattern is monotonically increasing.
9 march 2022 11:06 pm
Confusion in low ends with median?
Amazing video
can't we go with two functions:
cnt1+= countSmallerThan(a[i],mid)
cnt2+= countSmallerThanEqualTo(a[i],mid)
mid_ind = (n+m)/2
if(mid_ind > cnt1 && mid_ind
Editing : mid_ind = ((n*m)/2) + 1
search space can be minimum and max number of the matrix.
explaination is very confusing
yes, it is confusing, I didn't understand why low=1, high=1e9
Thanks Bhaiya
Awesome explanation 🔥🔥🔥 Hattttttttttttttttttttttttttttss offffffffffffffffffffffffffffffff vaiya...
Why are we using the condition
because bro, we have to count the numbers less than or equal to itself. For example, in [1, 2, 3, 4, 5], if you find numbers less than 3, you find only 2 numbers. If you consider only less than 3 here, it wouldn't practically give you answer . It would be easy to pick median from the odd number of elements, the question has stated the same that the array has odd number of elements.
we take
Thank you bhaiya very clear to me it is was
not clear :(
please rerecord this video
Awesome bro 🔥🔥🔥🔥
Please make a video on "Kth smallest element in a row and column wise sorted matrix" using Binary Search.
th-cam.com/video/HuOcDlB1uXk/w-d-xo.html
understood
can anyone tell me whether the search space be b/w 1 to max-element of the given matrix? Also, what is the intuition behind taking such a large search space?
search space can be the minimum and max number of the matrix.
@@SudhanshuKumar-lp1nr thanks sir
@@SudhanshuKumar-lp1nr can u tell me the intuition behind taking this large search space?
my search space was smaller than the search space used in the video, so I decided to take a smaller search space
I have tried using the smaller search space between - min and max of matrix but on gfg it passes some test case while it gives segment ation error on some. I dont know why
Can you please let me know why this program giving me runtime error?
int row=matrix.size();
int col=matrix[0].size();
vector arr(row*col);
for(int i=0;i
for(int j=0;i
it should be vector arr; , don't specify the size because vector arr(row*col) will create vector with '0', and further insertion will take place after it.. i think thats why its not working
I had a doubt , for the sub problem of finding the index just greater than a given value , can we find the last occurrence of that element and then last occurence - 0 will give the elements lesser than and equal to the given value?
it is much trickier to find the last occurrence of an element than finding an element just greater than itself
Bro one thing, in explanation you are referring median position as 5 which is (n*m+1)/2 and in code you are comparing with
(n*m)/2
index start from 0
code gave error in the problem link :)
Any help!!
What does the constraint 1 to 10^9 mean
Open the question link in the description.
We can even set the low = min value in matrix, high = max value in matrix
@@manvikarya725 in order to find that we will waste time.
@@takeUforward It will take only O(n) time, to find min and max, because 0th and (m-1)th index of row will contain these values, then it will not exceed time
@@sauravkumargupta2594 why do you want to use some extra time 👀
very confusing
other videos are good explained but this just goes over the head
any one can explain me why we used mid = (low + high) >> 1 rather then mid=(low+high)/2
(low + high) >> 1 means left shift low+high by 1 bit , which is nothing but (low+high)/2
this is giving tle in gfg
wrong code
Gfg is wrong, try lc :)
@@takeUforward bhaiya its giving wrong output in gfg plz you try and if its really wrong then pin a comment becoz many of them wasted their whole day in seeing what is wrong in this code like me.