New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Carpet and Boxes

Contributed by

Amit Shaw

Medium

0/80

Avg time to solve 20 mins

Success Rate 70 %

0 upvotes

Problem Statement

You are given 'N' boxes of width 1 unit. You are also given an array 'POSITION' which denotes the positions of the boxes, e.g POSITION[ i ] denotes the position of the ith box. You need to cover any 'K' boxes with a carpet.

Find the minimum length of the carpet to cover any 'K' boxes.

Example:

Input: ‘N’ = 3, ‘K’ = 2, 'POSITION' = [2, 3, 6] 

Output: 2

 There are two possible ways to cover exactly two boxes. One covers the boxes at positions 2 and 3 and the other at positions 3 and 6. The carpet lengths required for both ways are 2 ( Since boxes are at positions 2 and 3 each having width 1) and 4, respectively. So the minimum length of the carpet is 2.

Detailed explanation ( Input/output format, Notes, Constraints, Images )

Input Format :

The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains two integers ‘N’ and ‘K’ denoting the length of the array 'POSITION' and the number of boxes to be covered respectively.
The second line of each test case contains ‘N’ integers denoting the position of the boxes.

Output format :

For each test case, return the minimum length of the carpet to cover any ‘K’ boxes.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^5
K > 0
1 <= POSITION[i] <= 10^9

Time Limit: 1 sec

Sample Input 1 :

Sample Output 1 :

5
1

Explanation Of Sample Input 1 :

For the first case:
There are two possible ways to cover exactly three boxes. One covers the boxes at positions 2, 4 and 6 and the other at positions 4, 6 and 9. The carpet lengths required for both ways are 5 and 6, respectively. So the minimum length of the carpet is 5. 

For the second case:
Since we need to cover only one box, the minimum length of the carpet is 1.

Sample Input 2 :

2
5 2
100 2 95 145 47 
1 1
100

Sample Output 2 :

6
1

Auto

Console