Minimizing Array sum with groupings

By
Sohaib
-
0
8
Adv1


Adv2

Given an array arr[] of integers, the duty is to reduce its sum by creating teams of as much as dimension ok. Every group consists of ok parts chosen from the array such that the sum of the group is ok instances the minimal worth among the many chosen parts (ok*min(arr1, arr2, ___, arrk), the place arr1, arr2___, arrk are the ok parts which you have got chosen in your group). You may create an arbitrary variety of teams, and the group dimension will be lower than or equal to ok. Your job is to seek out the utmost attainable discount within the sum of the array parts after creating such teams.

Examples:

Enter: n = 3, ok = 2, arr[] = {4, 4, 8}
Output: 4
Clarification: You may make a gaggle of dimension 2 – index(1, 2) then initially sum was 4 + 8 = 12 however after the group sum turns into 4 + 4 = 8, So you have got decreased 4 from the precise sum of those two parts and you cannot group different parts to lower total sum additional. So it’s going to stay the identical.

Enter: n = 2, ok = 1, arr[] = {1427, 110}
Output: 0
Clarification: The group dimension is 1 so you cannot group any 2 or extra parts, So the sum will stay the identical..

Strategy: To unravel the  downside observe the beneath thought:

As we’ve to lower the utmost sum so we are going to use the Grasping method right here and can group the best numbers with the bottom numbers in order that sum will lower most. We are going to do the identical course of till all of the aspect is grouped. And to get the weather so as in order that we will group effectively we are going to use sorting.

Illustration:

Let’s focus on a small instance: arr[] = {6, 1, 10, 2, 4}, ok = 3. 

Now we are going to kind the array -> {1, 2, 4, 6, 10} and after this, we are going to group the utmost with the minimal like this we are going to make a gaggle of {1, 6, 10} in order that we will lower the sum by (10-1+6-1) = 14 from there, and one other group we are going to make of {2, 4} and we are going to lower the sum by (4-2 = 2) from there so on this means we are going to lower the sum by 16 in whole.

Steps that have been to observe the above method:

  • Kind the preliminary array
  • Verify for the sting case of ok is 0 or 1, as on this case, we can not scale back the general sum additional.
  • For each extraordinarily reverse aspect of this array,
    • If the present group dimension is lower than ok, add up the distinction between it and the present smallest aspect within the group.
    • If the group turns into full, create one other group.
    • And, change the present minimal aspect as properly.
  • Lastly, return the ans, which shops the utmost attainable lower within the total sum of the array.

Beneath is the code to implement the above steps:

C++

#embody <bits/stdc++.h>

utilizing namespace std;

  

int maxDecr(int n, vector<int>& arr, int ok)

{

  

    

    kind(arr.start(), arr.finish());

  

    

    if (ok == 0 or ok == 1)

        return 0;

  

    

    

    

    

    int ans = 0, j = 0, dimension = 1, i = n - 1;

  

    

    whereas (i > j) {

  

        

        if (dimension != ok) {

            ans += (arr[i] - arr[j]);

            dimension++;

        }

  

        

        

        else {

            j++;

            i++;

            dimension = 1;

        }

        i--;

    }

    return ans;

}

  

int major()

{

  

    

    

    int n = 5, ok = 3;

  

    

    vector<int> arr = { 6, 1, 10, 2, 4 };

  

    

    cout << maxDecr(n, arr, ok) << endl;

    return 0;

}

Time Complexity: O(n*logn), the place n is the variety of parts of the array.
Auxiliary House: O(1)

Adv3