Lazy Santa

Easy
0/40
5 upvotes
Asked in companies
IBMAppleSimplify VMS

Problem statement

It’s christmas and Santa is here with ‘K’ gifts. There are ‘N’ children in the park who are standing in a straight line, and not crowding up due to COVID restrictions. You are given an array “distance” containing ‘N’ integers where “distance[i]” denotes the distance of the ith child from the gate of the park in meters. Each child stands at a different distance from the gate.

Since Santa is still on his reindeer, he can land at any position in the park. But once he lands on the ground, he uses his feet to walk. Santa is very lazy and is requesting you to find the minimum distance he needs to travel on his feet so that he can distribute all the ‘K’ gifts to ‘K’ different children.

Example: 
Let there be 6 children and 3 gifts. If the position of the children is [3, 6, 7, 10, 17, 25], the minimum distance Santa has to walk is 4m which can be achieved in many ways, one of them being Santa landing at the 1st child and walking till the 3rd child (distance = (6m - 3m) + (7m - 6m) = 4m).
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains two space-separated integers, ‘N’ and ‘K’ denoting the number of children and number of gifts respectively.

The next line contains ‘N’ space-separated integers denoting the array “distance”.
Output Format : 
For each test case, return an integer denoting the minimum distance Santa has to travel.

Output for each test case will be printed in a new line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given functions.
Constraints: 
1 <= T <= 100
1 <= N <= 10000
1 <= K <= 10000
1 <= distance[i] < 10^9


Time Limit: 1 sec
Sample Input 1 :
2
6 3
6 7 3 25 17 10
5 5
10 13 15 16 18
Sample Output 1:
4
8

Explanation For Sample Output 1:

In the first case, Santa lands at the 1st child and walks till the 3rd child. Distance = (6m - 3m) + (7m - 6m) = 4m.
In the second case, Santa lands at the 2nd child and walks till the 5th child. Distance = (13m - 10m) + (15m - 13m) + (16m - 15m) + (18m - 16m) =  3m + 2m + 1m + 2m = 8m
Sample Input 2 :
2
3 1
2 10 4
2 2
4 2
Sample Output 2 :
0
2
Hint

Does it make sense in distributing the gifts to children who are not adjacent to each other?

Approaches (1)
Brute Force

We can note that it is always optimal to distribute gifts to ‘K’ children who are adjacent to each other. 

 

For example, if the position of children are [2, 4, 7] and K = 2, it is optimal to give gifts to children with positions 2 and 4. If the positions were to be [2, 5, 7], it is optimal to give gifts to children at positions 5 and 7. In general, if the positions are [p1, p2, p3] where p1 < p2 < p3 and K = 2, it is never optimal to distribute gifts to children at p1 and p3.

 

We can start by sorting the “distance” array, so that we get the positions of children in increasing order. Then we can calculate the minimum distance Santa has to travel in case he lands at the ith child for each ‘i’ where 1 <= i <= N - K + 1 and walks towards the right(or increasing distance from park’s gate).
 

Note that if Santa lands on a child with index greater than N - K + 1, the number of children to his right are less than K and so he cannot distribute all gifts.

 

We can do that by simply iterating through each ‘i’ from 1 to N - K + 1, and for each ‘i’ calculate distance[i + K - 1] - distance[i] (which means we distributed gifts to each child with index between [i, i + K - 1]). We then have to store the minimum of all the distances to get the overall minimum distance.

 

Algorithm:

 

  • Sort the array “distance”.
  • Create a variable named “minDistance” and initialize it with a large enough value. In our case 10^9 should be enough.
  • Iterate using a variable ‘i’ from 1 till N - K + 1, both inclusive.
    • For each value of ‘i’, update “minDistance” to be the minimum of “minDistance” and (distance[i + K - 1] - distance[i]).
  • Return minDistance.
Time Complexity

O(N * log(N)), where ‘N’ denotes the number of children.

 

Note that we sort the array initially which costs N * log(N) operations. After that we iterate through the entire array, but at each iteration we just perform constant number of operations and therefore the overall complexity of the solution is N * log(N) + N * C where ‘C’ is a constant. That is equivalent to O(N * log(N)).

Space Complexity

O(1)

 

Constant extra space is required. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Lazy Santa
Full screen
Console