PAHADE

PROBLEM STATEMENT

Ninja’s grandfather is very interested in listening to the multiplication table from our ninja, and if the ninja makes some mistake, he is not allowed to go outside to play. So our ninja started learning tables and learned all the tables perfectly. But his grandfather now comes with a new idea that now he gives three numbers to ninja ‘M’, ’N’, ‘K’. ‘M’ is the height of the multiplication table, so starting from the table of ‘1’ he has to write the table up to ‘ N’, and from that table he has to find the ‘Kth’ smallest number from that table.

So your task is to help Ninja find the ‘Kth’ smallest number in the table given height ‘M’, length ‘N’, and a positive integer ‘K’.

Example:

‘M’ is ‘3’, ‘N’ is ‘4’and ‘K’ is ‘5’. For this input, multiplication table is:

Example

So the ‘5th’ smallest number is ‘3’(‘1’, ‘2’, ‘3’, ‘3’, ‘4’, ‘4’, ‘6’, ‘6’, ‘8’, ‘9’, ‘12’)

Input Format:

The first line of input contains a ‘T’ number of test cases.

In the second line, three space-separated integers ‘M’, ‘N', and ‘K' denoting height and length of the multiplication table, and ‘K’ represents the ‘Kth’ smallest number which we have to find from the multiplication table.

Output Format:

For each test case, print a single line containing a single integer denoting the ‘Kth’ smallest number.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10000
1 <= M,N <= 10 ^ 7
1<= K <= M*N

Time Limit: 1 second.

Approach 1

The simplest approach is that first, we define a matrix ‘Mat’ of size ‘((M+1) * (N+1))’
Now we make a multiplication table on the basis of a given value as each matrix element is equal to the product of its indices i.e. ‘i’ row and ‘j’ column element are equal to the ‘i * j’. So in this way filled our matrix.
- Iterate a loop ‘i’ from ‘1’ to ‘m’
  - Iterate another nested loop ‘j’ from ‘1’ to ‘N’
    - ‘Mat[i][j] = i * j’.
Now we fill all the elements in our array ‘arr’ and use sorting to sort that array.
Now we can easily find the ‘Kth’ smallest element from the array and return it as our answer.

Try Problem

Approach 2

As we know the matrix is sorted so we can think of a binary search to find the kth smallest element. To optimize our Brute force approach we now use the concept of binary search.

Here is the algorithm:

First, we define three variables ‘low’, ‘high’, and ‘mid’.
Now we initialize ‘low’ as ‘1’ and ‘high’ as ‘N * M’, as we know ‘Kth’ smallest element lies between ‘1’ and ‘N * M’.
Find the ‘mid’ element between the ‘low’ and ‘high’ elements.
If the number of elements is less than the ‘mid’ is greater than or equal to ‘K’, then update ‘high’ to ‘mid-1’ as the ‘Kth’ smallest element lies between ‘low’ and ‘mid’.
If the number of elements less than ‘mid’ is less than the ‘K’, then we update low to ‘mid+1’ as the ‘Kth’ smallest element lies between ‘mid’ and ‘high’.
As the elements in the ‘ith’ row are the multiple of ‘i’, the number of elements less than mid in the ‘ith’ row can be calculated easily by min(mid / i, M).
Perform binary search till ‘low’ is less than or equal to ‘high’ and return ‘high + 1’ as the ‘Kth’ smallest element as our final answer.