Lazy Santa
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).

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

Question

Lazy Santa

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).

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

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1)

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

Time Complexity: O(nlogn)Explanation:

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)).

Python (3.5)

'''

	Time Complexity : O(N * log(N))

	Space Complexity : O(1)



	where 'N' denotes the number of children.

'''



def lazySanta(distance, K):



    # Sort the array

    distance.sort()

    n = len(distance)



    # Initialize the result with large value.

    minDis = 10 ** 9 + 5



    # For each child calculate the minimum distance Santa has to travel.

    for i in range(n - K + 1):

        minDis = min(minDis, distance[i + K - 1] - distance[i])



    # Return answer

    return minDis

C++ (g++ 5.4)

/*

	Time Complexity : O(N * log(N))

	Space Complexity : O(1)



	where 'N' denotes the number of children.

*/



#include 

#include 



int lazySanta(vector distance, int K)

{

	

	// Sort the array so that we get the positions of children in increasing order

	sort(distance.begin(), distance.end());

	

	// Store the number of children

	int N = distance.size();

	

	// Initialize the result with a large value

	int minDistance = INT_MAX;

	

	// For each child calculate the minimum distance Santa has to travel in case he lands at the ith child

	// and walks towards the right(or increasing distance from park gate)

	for(int i = 0; i + K - 1 < N; i++)

	{

		minDistance = min(minDistance, distance[i + K - 1] - distance[i]);

	}

	

	// Return the calculated minimum distance

	return minDistance;

}

Java (SE 1.8)

/*

	Time Complexity : O(N * log(N))

	Space Complexity : O(1)



	where 'N' denotes the number of children.

*/



import java.util.*;



public class Solution 

{

    public static int lazySanta(int[] distance, int K)

    {



        // Sort the array so that we get the positions of children in increasing order

        Arrays.sort(distance);

        

        // Store the number of children

        int N = distance.length;



        // Initialize the result with a large value

        int minDistance = Integer.MAX_VALUE;



        // For each child calculate the minimum distance Santa has to travel in case he lands at the ith child

        // and walks towards the right(or increasing distance from park gate)

        for(int i = 0; i + K - 1 < N; i++)

        {

            minDistance = Math.min(minDistance, distance[i + K - 1] - distance[i]);

        }



        // Return the calculated minimum distance

        return minDistance;

	}

}

Example:

Input Format:

Output Format :

Note:

Constraints:

Top SimplifyVMS Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern