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;
}
Last updated
Was this helpful?