Minimum Array Reduction

Given some array, find the minimum possible reduction/cost.

• Your process must go as follows:

  • Remove any two elements that are different (index-wise)

  • Add the sum of these elements as a new element into the array

  • Your total cost will be the total sum of these elements in the previous step.

  • Continue this process until you are unable to remove 2 elements.

int reductionCost(vector < int > nums) {
    int min_cost = 0;

    int i = 1;
    while (nums.size() != 1) {
        sort(nums.begin(), nums.end());
        int cost = nums[i - 1] + nums[i];
        min_cost += cost;
        nums.push_back(cost);
        nums.erase(nums.begin(), nums.begin() + 2);
    }
    return min_cost;
}

int main()
{
    cout << reductionCost(vector<int>() = { 1,2,3,4 }) << endl;
    cout << reductionCost(vector<int>() = { 1,2,3 }) << endl;

}