Would anyone like to share their solution to CSES Multiplication Table? There’s no solution for it in USACO guide, and I can’t see how binary search could be applied. Thanks in advance!
Define f(x) = the number of numbers in the table that is less than or equal to x
You simply want to find the least number such that f(x) >= (n * n + 1) / 2 (this can be done with a binary search)
Try to think about how to calculate f(x) in O(n).
that is the part I struggled with
Actually I got it now, the mention of O(n) really helped.
Can you post your solution? I am still struggling with this problem.