0

# Batch Photography

Difficulty: HARD
Contributed By
Avg. time to solve
30 min
Success Rate
70%

Problem Statement

#### Example: Let the resolutions be [1, 5, 2] and K = 2. So there is only one way of dividing the array, which is a single group of all three elements. The error is therefore 5 - 1 = 4.

##### Input Format:
``````The first line contains ‘T’, denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘K’, denoting the number of photos and the minimum size of each batch.

The second line of each test case contains an array ‘photos’ of ‘N’ space-separated integers, denoting the resolution of the ith photo.
``````
##### Output Format:
``````For each test case, print an integer denoting the minimum ‘maximum error’.
``````
##### Note:
``````You are not required to print the expected output. It has already been taken care of. Just implement the function.
``````
##### Constraints:
``````1 <= T <= 10
1 <= K <= N <= 10^4
1 <= photos[i] <= 10^9

Time Limit: 1 sec
``````
##### Sample Input 1:
``````2
5 2
50 110 130 40 120
4 1
2 3 4 1
``````
##### Sample Output 1:
``````20
0
``````
##### Explanation for Sample Input 1:
``````In the first test case, the photos should be split into 2 groups: [40, 50] and [110, 120, 130]. The processing time of the first group is 10, and the processing time of the second group is 20. The maximum between 10 and 20 is 20. It is impossible to split the photos into groups in such a way that the processing time of division is less than 20.
In the second test case, the photos should be split into four groups, each containing one photo. So the minimal possible processing time of a division is 0.
``````
##### Sample Input 2:
``````2
5 2
5 7 3 3 5
3 2
1 2 3
``````
##### Sample Output 2:
``````2
2
``````
Console