Last Updated: 1 Jan, 2022
Take Out Chocolates
Moderate
On your birthday, your friends gifted you 'N' boxes of chocolates, which are represented as an array 'A' of 'N' positive integers where 'A[i]' denotes the number of chocolates in the i-th box. You want to give these boxes as return gifts to your guests but with an equal number of chocolates in each box. For that, you are going to perform the following operation on the boxes, where each operation is as follows:
Choose a positive integer 'x'.
If any of the boxes contains more than 'x' chocolates, take out the extra chocolates from that box, i.e., if 'A[i]' > 'x', make 'A[i]' = 'x' ( for all 'i' where 1 <= 'i' <= 'N')
The cost of an operation is the total number of chocolates taken out from all the boxes, i.e., cost = (sum of 'A' before operation) - (sum of 'A' after operation).
Your task is to find the minimum number of operations such that there is an equal number of chocolates in each box and the cost of each operation does not exceed 'K'.
Note :
1. 'x' can be any positive integer of your choice. It may or may not be present in array 'A'.
2. 'K' is large enough to have at least one 'x' for the operation.
Example :
N = 4
K = 5
A = [ 5, 2, 3, 4 ]
In the first operation, choose x = 3, the updated array 'A' becomes [3, 2, 3, 3]. The cost of this operation is (5+2+3+4)-(3+2+3+3) = 3.
In the second operation, choose x = 2, the updated array 'A' becomes [2, 2, 2, 2]. The cost of this operation is (3+2+3+3)-(2+2+2+2) = 3.
After the second operation, all elements in array 'A' become equal. Hence return 2 as our final answer.
We can't choose x = 2 in our first operation, because (5+2+3+4)-(2+2+2+2) = 6 which exceeds K = 5.
Input Format :
The first line contains an integer 'T', denoting the number of test cases.
Then the test cases follow:
The first line of each test case contains two space-separated integers, 'N' and 'K', denoting the number of boxes (or size of array 'A') and maximum cost of an operation, respectively.
The next line contains 'N' integers, denoting the number of chocolates in each box (or array 'A' elements).
Output Format :
For each test case, print an integer denoting the minimum number of operations needed to perform on array 'A' to make all elements equal.
Print the output of each test case in a new line.
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 <= 'N' <= 10^5
N <= 'K' <= 10^9
1 <= 'A[i]' <= 10^5
Sum of 'N' over all test cases doesn’t exceed 10^5.
Time Limit: 1 sec
Approaches
Approach:
Our task is to make all elements in the array equal. The optimal way is to make the rest of the 'N-1' elements equal to the smallest element of the array.
- Sort the array 'A' in decreasing order of elements.
- Now perform operations in the following order: The first element is made equal to the second element, then both elements are made equal to the third element, and so on.
- While performing the above changes, keep track of the sum of differences that have occurred till the moment.
- While working on the 'A[1]', the sum of difference will be ('A[1]' - 'A[2]').
- While working on element 'A[2]', the sum of difference will be: existing difference + 2 * ('A[2]' - 'A[3]'), as both 'A[1]' and 'A[2]' will be changed to 'A[3]' simultaneously. Look at the following example:
- A = [7, 5, 4, 2]
- First, 'A[1]' will be changed to 'A[2]', the updated array 'A' becomes [5, 5, 4, 2] and the sum of differences is: 7-5 = 2.
- Then, both 'A[1]' and 'A[2]' will be changed to 'A[3]', the updated array 'A' becomes [4, 4, 4, 2] and sum of differences is: 2 + 2 * (5 - 4) = 4.
- And repeat the same for the rest of all elements.
- While changing 'A[i-1]' to 'A[i]', if the sum of differences exceeds 'K', do the following.
- Find optimal 'x' to which 'A[i-1]' can be changed in the current operation only.
- Then increment the required number of operations and try to change 'x' into 'A[i]'.
- There may be the case that it needs multiple operations for 'x' to reach 'A[i]', but those operations should be performed together using some maths.
- Assume we can change 'x' into 'x+d' in one operation, so perform '(A[i] - x) / d' operations together and the next operation will definitely change it to 'A[i]'.
- As our final answer, return the number of times the sum exceeded value 'K'.
Algorithm:
- Sort the array 'A' in non-increasing order.
- Initialize a variable 'sum' to store the sum of differences and another variable 'ans' to hold the final answer.
- Iterate a loop for 'i' = 2 to 'N'.
- Here 'A[i-1]' will be changed to 'A[i]'.
- Calculate the gap between both elements; 'gap' = 'A[i-1]' - 'A[i]'.
- We already have a sum of differences as 'sum' and a total of 'i' elements change together, so the gap that can be covered in the current operation is 'x' = '(k - sum) / (i - 1)'.
- If the 'gap' needs more steps than available 'x'.
- Increment 'ans' by 1, denoting that the current operation is complete.
- Calculate the remaining difference from 'A[i]'; 'left' = 'gap - x';
- Calculate the difference that can be reduced in one operation; 'd' = 'k / (i - 1)'.
- If multiple such operations are needed to cover the difference, perform all of them together; 'ans' += 'left / d'.
- Calculate the updated remaining difference from 'A[i]'; 'left' = 'left % d';
- Use the remaining difference as the sum of differences; 'sum' = 'left * (i - 1)'.
- Else, change all 'A[1 … i-1]' to 'A[i]' and update sum of differences; 'sum' += 'gap * (i - 1)';
- We cover a total difference of 'K' units in the above operations and then increment our answer. So, at last, if 'sum' is non-zero, one more operation is needed, hence increment 'ans' by 1.
- Return 'ans' as our final answer.