Minimizing Array sum with groupings

Given an array arr[] of integers, the task is to minimize its sum by creating groups of up to size k. Each group consists of k elements selected from the array such that the sum of the group is k times the minimum value among the chosen elements (k*min(arr1, arr2, ___, arrk), where arr1, arr2___, arrk are the k elements which you have chosen in your group). You can create an arbitrary number of groups, and the group size can be less than or equal to k. Your task is to find the maximum possible reduction in the sum of the array elements after creating such groups.

Examples:

Input: n = 3, k = 2, arr[] = {4, 4, 8}
Output: 4
Explanation: You can make a group of size 2 – index(1, 2) then initially sum was 4 + 8 = 12 but after the group sum becomes 4 + 4 = 8, So you have decreased 4 from the actual sum of these two elements and you can not group other elements to decrease overall sum further. So it will remain the same.

Input: n = 2, k = 1, arr[] = {1427, 110}
Output: 0
Explanation: The group size is 1 so you can not group any 2 or more elements, So the sum will remain the same..

Approach: To solve the  problem follow the below idea:

As we have to decrease the maximum sum so we will use the Greedy approach here and will group the highest numbers with the lowest numbers so that sum will decrease maximum. We will do the same process until all the element is grouped. And to get the elements in order so that we can group efficiently we will use sorting.

Illustration:

Let’s discuss a small example: arr[] = {6, 1, 10, 2, 4}, k = 3. 

Now we will sort the array -> {1, 2, 4, 6, 10} and after this, we will group the maximum with the minimum like this we will make a group of {1, 6, 10} so that we can decrease the sum by (10-1+6-1) = 14 from there, and another group we will make of {2, 4} and we will decrease the sum by (4-2 = 2) from there so in this way we will decrease the sum by 16 in total.

Steps that were to follow the above approach:

• Sort the initial array
• Check for the edge case of k is 0 or 1, as in this case, we cannot reduce the overall sum further.
• For every extremely opposite element of this array,
  • If the current group size is less than k, add up the difference between it and the current smallest element in the group.
  • If the group becomes full, create another group.
  • And, change the current minimum element as well.
• Finally, return the ans, which stores the maximum possible decrease in the overall sum of the array.

Below is the code to implement the above steps:

Time Complexity: O(n*logn), where n is the number of elements of the array.
Auxiliary Space: O(1)

Given an array arr[] of integers, the task is to minimize its sum by creating groups of up to size k. Each group consists of k elements selected from the array such that the sum of the group is k times the minimum value among the chosen elements (k*min(arr1, arr2, ___, arrk), where arr1, arr2___, arrk are the k elements which you have chosen in your group). You can create an arbitrary number of groups, and the group size can be less than or equal to k. Your task is to find the maximum possible reduction in the sum of the array elements after creating such groups.

Examples:

Input: n = 3, k = 2, arr[] = {4, 4, 8}
Output: 4
Explanation: You can make a group of size 2 – index(1, 2) then initially sum was 4 + 8 = 12 but after the group sum becomes 4 + 4 = 8, So you have decreased 4 from the actual sum of these two elements and you can not group other elements to decrease overall sum further. So it will remain the same.

Input: n = 2, k = 1, arr[] = {1427, 110}
Output: 0
Explanation: The group size is 1 so you can not group any 2 or more elements, So the sum will remain the same..

Approach: To solve the  problem follow the below idea:

As we have to decrease the maximum sum so we will use the Greedy approach here and will group the highest numbers with the lowest numbers so that sum will decrease maximum. We will do the same process until all the element is grouped. And to get the elements in order so that we can group efficiently we will use sorting.

Illustration:

Let’s discuss a small example: arr[] = {6, 1, 10, 2, 4}, k = 3. 

Now we will sort the array -> {1, 2, 4, 6, 10} and after this, we will group the maximum with the minimum like this we will make a group of {1, 6, 10} so that we can decrease the sum by (10-1+6-1) = 14 from there, and another group we will make of {2, 4} and we will decrease the sum by (4-2 = 2) from there so in this way we will decrease the sum by 16 in total.

Steps that were to follow the above approach:

• Sort the initial array
• Check for the edge case of k is 0 or 1, as in this case, we cannot reduce the overall sum further.
• For every extremely opposite element of this array,
  • If the current group size is less than k, add up the difference between it and the current smallest element in the group.
  • If the group becomes full, create another group.
  • And, change the current minimum element as well.
• Finally, return the ans, which stores the maximum possible decrease in the overall sum of the array.

Below is the code to implement the above steps:

Time Complexity: O(n*logn), where n is the number of elements of the array.
Auxiliary Space: O(1)