Last Updated: 22 Feb, 2021
Chocolates With Magical Number
Easy
Asked in companies
Ninja is planning to give ‘PACKET’ of 'N' chocolates to his friend on his birthday. Each chocolate in ‘PACKET’ has a non-negative sweetness level that denotes how sweet the chocolate is. He wants to give these chocolates to his friend such that the absolute difference between chocolate with maximum sweetness and minimum sweetness should be as minimum as possible.
In order to do this, Ninja uses a magic number, 'K' under the following conditions:
1. Using this magical number, Ninja can either increase or decrease the sweetness of each chocolate.
2. After increasing or decreasing the sweetness, all the new sweetness values must be non-negative.
3. Ninja must use this magic number on each chocolate exactly once.
For Example :
For ‘PACKETS’ = [1, 2, 3, 4, 5] and 'K' = 1, the absolute difference between two chocolates with maximum (5) and minimum (1) sweetness is 4. Now in order to minimize this value, Ninja increases [1, 2, 3] and decreases [4, 5] by 1 (‘K’ = 1). So, ‘PACKET’ becomes [2,3,4,3,4]. Now, the absolute difference between the two chocolates with maximum (4) and minimum (2) sweetness is 2 which is the minimum possible.
As Ninja is busy preparing for the party, he asks you for help. Can you help Ninja determine the minimum possible difference between the maximum and minimum sweetness of chocolates in 'PACKET’ after using the magic number 'K'?
Input Format :
The first line 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 two single space-separated integers 'N' and 'K' denoting the number of chocolates in the 'PACKET' and the magic number, respectively.
The second line of each test case contains 'N' single space-separated integers, denoting the sweetness of each chocolate in 'PACKET'.
Output Format :
For each test case, print the minimum possible difference between the maximum and minimum sweetness value of chocolates in the array/list ‘PACKET’.
Print the output of each test case in a separate line.
Note :
You are not required to print the expected output, and it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 100
1 <= N <= 10^5
1 <= K <= 10^5
1 <= PACKET[i] <= 10^5
Where 'T' is the number of test cases, 'N' denotes the number of chocolates in the given array/list 'PACKET' and 'K' denotes the given magic number, respectively. 'PACKET[i]' denotes the sweetness of the i'th chocolate.
Time Limit : 1 sec
Approaches
The main observation while solving this problem is that after every update to ‘PACKET’, only the difference between the largest and smallest sweetness level of chocolate matters to us.
The main idea behind this approach is to sort ‘PACKETS’ in increasing order. Then for all the chocolates in the ‘PACKET’, check if subtracting the sweetness level of ‘i’th chocolate by ‘K’ (i.e. PACKET[i]’ - ’K’) or increasing its value by ‘K’ (i.e. ‘PACKET[i]’ + ’K’) makes any changes in our result or not.
Here is the complete algorithm :
- Sort the ‘PACKET’ in increasing order and initialize three variables ‘BIG’ = ‘PACKET[N - 1]’ i.e. the largest value in ‘PACKET’, ‘SMALL’ = ‘PACKET[0]’ i.e. the smallest value in ‘PACKET’ and ‘MIN_DIFF’ to store the difference between the largest and the smallest sweetness value.
- Now iterate the ‘PACKET’ and for each chocolate, do the following:
- If subtracting and adding ‘K’ to the chocolate does not change ‘SMALL’ and ‘BIG’ respectively then do nothing. Following are those two cases:
- ‘PACKET[i] - ‘K’’ >= ‘SMALL’
- ‘PACKET[i] + ‘K’’ <= ‘BIG’
- Else, either the subtraction (‘PACKET[i]’ - ‘K’) will yield the smaller number or the addition (‘PACKET[i]’ - ‘K’) will result in a greater number. Update our ‘SMALL’ or ‘BIG’ variables accordingly:
- If ‘BIG’ - ‘PACKET[i]’ - ‘K’ results in a smaller difference then update ‘SMALL’.
- Else update ‘BIG’.
- If subtracting and adding ‘K’ to the chocolate does not change ‘SMALL’ and ‘BIG’ respectively then do nothing. Following are those two cases:
- Finally, return the minimum of ‘MIN_DIFF’ and ‘BIG’ - ‘SMALL’.