Take Out Chocolates

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

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.

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

For test case 1: In the first operation, choose x = 3, the updated array 'A' becomes [3, 1, 3, 3, 3]. The cost of this operation is (3+1+3+6+3)-(3+1+3+3+3) = 3. In the second operation, choose x = 2, the updated array 'A' becomes [2, 1, 2, 2, 2]. The cost of this operation is (3+1+3+3+3)-(2+1+2+2+2) = 4. In the third operation, choose x = 1, the updated array 'A' becomes [1, 1, 1, 1, 1]. The cost of this operation is (2+1+2+2+2)-(1+1+1+1+1) = 4. After the third operation, all elements in array 'A' become equal. Hence return 3 as our final answer. For test case 2: In the first operation, choose x = 2, the updated array 'A' becomes [2, 2, 2, 2, 2]. The cost of this operation is (2+2+2+2+3)-(2+2+2+2+2) = 1. After the first operation, all elements in array 'A' become equal. Hence return 1 as our final answer.

Greedy + Maths

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.

Time Complexity

O(N logN), where 'N' is the number of elements in array 'A'.

Sorting an array of 'N' size takes O(N * logN). After that we traversed the array only once. Hence overall time complexity becomes O(N logN).

Space Complexity

O(1)

We are using only constant space to store various sums and differences. Hence the overall space complexity becomes O(1).

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation for Sample Input 1 :

Sample Input 2 :

Sample Output 2 :