PAHADE

Easy
0/40
Average time to solve is 15m
2 upvotes
Asked in companies
UberGoogle inc

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’)
Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

2
2 3 6
3 2 5

Sample Output 1:

6
4

Explanation of Sample Input 1:

Test Case 1:

So for this test case ‘M’ is ‘2’, ‘N’ is ‘3’ and ‘K’ is ‘6’. Hence the multiplication would look like

Example

So the ‘6’ minimum element is ‘6’ (‘1’, ‘2’, ‘2’, ‘3’, ‘4’, ‘6’)


Test Case 2:

So for this test case ‘M’ is ‘3’, ‘N’ is ‘2’ and ‘k’ is ‘5’. Hence the multiplication would look like

Example

So the ‘5’ minimum element is ‘4’ (‘1’, ‘2’, ‘2’, ‘3’, ‘4’, ‘6’).
Sample Input 2:
2
1 3 2
2 4 6
Sample output 2:
2
4
Hint

Can we sort our elements?

Approaches (2)
Brute Force
  • 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.
Time Complexity

O((M * N) log(M * N)), where ‘M’ denotes the length of the multiplication and ‘N’ represents the length of the multiplication table.

 

As we are filling our matrix of size ‘M * N’ and sorting it.

Space Complexity

O(M * N), where ‘M’ denotes the length of the multiplication and ‘N’ represents the length of the multiplication table.

 

As we are filling our matrix of size ‘M * N’.

Code Solution
(100% EXP penalty)
PAHADE
Full screen
Console