Do binary search on X where X is the number of values in the matrix less than X. Thus initial low=1, high=n*m and then for every mid=(low+high)/2 calculate the number of values less than mid in the matrix and shift the low and high pointers accordingly.

To calculate the number of values less than mid in the matrix :-- num=0, then for each row i 1 to n: num+=min(m, (mid-1)/i)

I hope this gives you enough clarification of what to do! :)

Have you tried reading this?

Hi!

I solved this problem quite recently. My algorithm matched the one in the editorial, here's my explanation.

First of all, brute force can't work, that would need O(n·m) time. So, that's out of question.

But we do know one thing, that the number of multiples of a number n strictly less than a value x are always equal to . It's not too tough to see the correctness of this, and can be proven using elementary math.

Using this observation, we can run a binary search for such number x such that the number of multiples of numbers 1 to n are equal to k. But because we only consider the first m multiples of these numbers(as the table doesn't have numbers greater than this), the number of values less than a number x in the multiplication table ultimately amount to

The above value can be calculated in O(n) time. The work left is implementing a binary search that searches the interval 1, 2, ... , 25·10¹⁰ as the maximum value of answer can be n·m. The final time complexity of solution amounts to O(n·log(n·m)).

I hope my explanation makes sense. Please point out any errors. My solution can be found at 13549897.