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!