New update is available. Click here to update.

Last Updated: 28 Jan, 2021

Difficulty: Hard

```
‘ROW1’ : [2, 5, 8, 17] and ‘ROW2’ : [1, 4, 8, 13, 20]
```

```
If ‘ROW1’ is [2, 5, 8, 17] and ‘ROW2’ is [1, 4, 8, 13, 20], then Ninja picks the first plates from each rows, plate containing 2 ladoos from ‘ROW1’ and a plate containing 1 ladoo from ‘ROW2’.
Then he gives the plate with 1 Ladoo to the first person in line and places the other plate back to its position.
```

```
The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of each test case contains three single space-separated integers ‘N’, ‘M’ and ‘K’ where ‘N’ and ‘M’ denote the number of plates containing ladoos in ‘ROW1’ and ‘ROW2’ respectively and ‘K’ denotes the ‘K’th’ person in line waiting to be served.
The second line of each test case contains ‘N’ single space-separated integers, denoting the number of ladoos in each plate of the first row i.e. ‘ROW1’.
The third line of each test case contains ‘M’ single space-separated integers, denoting the number of ladoos in each plate of the second row i.e. ‘ROW2’.
```

```
For each test case, print an integer denoting the number of ladoos the K'th person will get.
Print the output of each test case in a separate line.
```

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

```
1 <= T <= 100
1 <= N, M, K <= 10^5
K <= (N + M)
0 <= ROW1[i], ROW2[i] <= 10^5
where ROW1[i] and ROW2[i] denote the number of Ladoos in i’th plates of ROW1 and ROW2 respectively.
Time Limit: 1 second
```

First of all, let’s think about what we want to find. We are given two sorted arrays i.e. *‘ROW1’* and* ‘ROW2’.* In these two arrays, we want to find the number of ladoos the *‘K'th’ *person will get. More specifically, we want to find the *‘K’th’* smallest element in the combined and sorted array. The simplest way to find the *‘K’th’* smallest element is to first merge the two arrays and then directly retrieve the *‘K’th’ *element.

Here is the algorithm :

- Declare a new array i.e.
*sortedRows*of length*M + N*in which we can store all the elements of ‘*ROW1’*and*‘ROW2’*. - Take three variables
*‘a’, ‘b’*and*‘c’*which are used to indicate the position of the current element of*‘ROW1’, ‘ROW2’*and ‘*sortedRows’*respectively. - We run a loop while
*‘a’ < ‘M’*and*‘b’ < ‘N’*:- If
*ROW1[a] <= ROW2[b]**sortedROw[c] = ROW1[a]**a++*

- Else
*sortedRow[c] = ROW2[b]**b++*

*c++*

- If
- If there is any element left of the
*‘ROW1’*then add the remaining elements of*‘ROW1’*i.e. run a loop while*‘a’ < ‘M’*:*sortedRow[c] = ROW1[a]**a++**c++*

- If there is any element left of the
*‘ROW2’*then add the remaining elements of*‘ROW2’*i.e. run a loop while*‘b’ < ‘N’*:*sortedRow[c] = ROW2[b]**b++**c++*

- Return the
*‘K’th’*element of the*sortedRow.*

We can improve the performance if we do not copy the full arrays, but stop when the resulting array has ‘*K*’ elements. We do not even need to create an additional array because we have to find only the ‘*K*’th’ element of the resultant array. So when we get the *‘K’th’ *element we break the loop and we can simply return our answer.

Here is the algorithm :

- Declare two variables
*‘i’*and*‘j’*which are used to indicate the position of the current element of*‘ROW1’, ‘ROW2’*respectively. - We run a loop while ‘
*i’ < ‘M'*and*‘j’ < ‘N’:*- If ‘
*i*’ +*‘j*’ == ‘*K*’- Return Math.min(
*ROW[ i ], ROW2[ j ]*)

- Return Math.min(
- If
*‘ROW1[ i ]’ <= ‘ROW2[ j ]’**i++*

- Else
*j++*

- If ‘
- If there is any element left in the
*‘ROW1’*while*‘i’ < ‘M' :*- If ‘
*i’*+ ‘*j’*== ‘*K’*- Return ‘
*ROW1[ i ]*’.

- Return ‘
*i++*

- If ‘
- If there is any element left of the
*‘ROW2’*while*‘j’ < ‘N’ :*- If ‘
*i’*+ ‘*j’*== ‘*K’*- Return ‘
*ROW2[ j ]*

- Return ‘
*j++*

- If ‘

We can make our algorithm more efficient by using a divide and conquer approach.

First we divide *‘K’ *by 2 i.e. *‘K’ / 2* and this value will be pointing to the indices of both the *ROW*’s. Now based on the comparison between both values we will call our recursive function.

Here is the algorithm :

- First we handle the base cases:
- If any of these ‘
*ROWs’*is empty then we will return ‘*K’th*’ element of other*‘ROW’.* - If
*‘K’*= 1 then return*min( ROW1[0], ROW2[0] ).*

- If any of these ‘
- Initialize a variable
*‘i’*which will point to the index of*‘ROW1’*and*‘j’*will point to the index of*‘ROW2’*.*‘i’ = min( M, K / 2) , ‘j’ = min(N, K / 2)*

- Now compare the values at
*ROW1[i]*and*ROW2[j]*and do the following:- If
*ROW1[i - 1] > ROW2[j - 1]*that means our*‘K’th’*value is present in the right of the*ROW2[j].*Now ‘*K*’ will become ‘*K’ - ‘j’.*- Return
*ninjaAndLadoos(ROW1, ROW2 + j, M, N - j, K - j).*

- Return
- Else value will be present in the right of ‘
*ROW1[i]’. So,*now ‘*K*’ will become ‘*K*’ - ‘*j*’.- Return
*ninjaAndLadoos(ROW1 + i, ROW2, M - i, N, K).*

- Return

- If

SIMILAR PROBLEMS

Three Sum

Posted: 24 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Negative To The End

Posted: 16 Dec, 2022

Difficulty: Easy

Sort 0s, 1s, 2s

Posted: 24 Dec, 2022

Difficulty: Easy

Fake Coin Problem

Posted: 24 Dec, 2022

Difficulty: Easy

Popular Interview Problems: