Problem: 1360H - Binary Median
I just wanted to share a solution to this problem that I couldn't catch in the editorial or the comments!
Observation 1:
We start with $$$2^m$$$ numbers and remove n of them. Therefore, our new set consists of ($$$2^m-n$$$) numbers. The median of this set of numbers is the number such that there are exactly $$$\lfloor (2^m-n-1)/2 \rfloor$$$ numbers less than it.
To find this number, we can binary search for the left most number in the range $$$[ 0 , 2^m-1 ]$$$ such that there at least $$$\lfloor (2^m-n-1)/2 \rfloor$$$ numbers less than it.
How do we check if a number "mid" has at least $$$\lfloor (2^m-n-1)/2 \rfloor$$$ numbers less than it?
Another binary search! => We can binary search on the set of removed numbers to find the index of the right most one such that it is $$$<= "mid"$$$. Then the numbers less than mid are simply $$$ mid - index$$$ !
My Submission for reference: 220757973
Thanks for reading!
Let me know if I have made any mistakes or you have any questions!