Why binary search is used to solve this ques
Why binary search is used to solve this ques
@jaiskid
Yes i have seen that but tell me why binary search and tell linear time method also irrespective of size of input .
@Ramitgoel
We know that our answer would lie between the range 0 to n. There is no direct formula to obtain the final answer so we have to try out all possible valid values. Our first option could be to try and check each value out but that could give us a TLE due to the problem constraints. So a simple brute force linear search is not likely to work. SInce our answer is in between 0 to n and obviously these numbers are sorted , we inferred that we could maybe apply binary search to obtain our result which would take O(log n) time and is likely to succeed given the constraints.
Answer to previous query , a linear time algorithm would be very similar to the binary search , infact easier.
Just run a loop from 0 to n , and call the isValid function for each value . Find the maximum value that would return true for the isValid function and that would be your answer. But again , this is likely to give a TLE.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
1 Like