Minimum number of moves to equalize list of numbers

Question

We have an array of n positive integers. An acceptable move is to increase all elements by 1 or 2 or 5 except one element. We need to find out minimum number of operations to make all array elements to some equal number.

After searching I found out one approach:

1. Find all the differences between non-minimum elements to the minimum element.
2. By using the coin change approach, find the minimum number of coins required to give the change for all differences.
3. Return the sum of all these minimum numbers of coins.

But this approach fails for this test case:

Array: 1,5,5

Minimum number of operations: 3 (1,5,5 -> 1,6,6 -> 6,6,11 -> 11,11,11).

By following the above approach I am getting 4.

Can anybody suggest the right approach?

Here is my source code:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

int input[10000];
int input1[10000];
int dp[4][1001];
int parent[4][1001];
int coins[4]={0,1,2,5};
int operation=0;
int main() {
    int t,n,i,j,count,sum,diff,prevdiff,min;
    for(i=1;i<1001;i++)
    {
        dp[0][i]=INT_MAX;
        parent[0][i]=INT_MAX;
    }
    for(i=0;i<4;i++)
    {
        dp[i][0]=0;
        parent[i][0]=-1;
    }
    for(i=1;i<1001;i++){
        for(j=1;j<4;j++){
            dp[j][i]=dp[j-1][i];
            parent[j][i]=parent[j-1][i];
            if(i>=coins[j]&&dp[3][i-coins[j]]<INT_MAX){

                if(dp[3][i-coins[j]]+1<dp[j][i]){
                    dp[j][i]=dp[3][i-coins[j]]+1;
                    parent[j][i]=j;
                }
            }
        }
    }
    cin>>t;
    while(t>0){
        cin>>n;
        min=INT_MAX;
        for(i=0;i<n;i++)
        {
            cin>>input[i];
            if(input[i]<min){
                min=input[i];
            }
            //input1[i]=input[i];
        }

        //sort(input,input+n);

        count=0;
        sum=0;

        for(i=0;i<n;i++){
            count=count+dp[3][input[i]-min];
        }

        cout<<count<<endl;
        t--;
    }
    /*
    for(i=1;i<1001;i++){
        if(dp[3][i]!=minCoins(i))
            cout<<dp[3][i]<<" "<<minCoins(i)<<endl;
    }
    */
    return 0;
}

Answer 1

Increasing all numbers except one by 1,2 or 5 is same as reducing that number by 1,2 or 5. So, this question can be converted to another problem in which -

We want to make all the numbers equal by using only 1 operation i.e. reducing a particular number by 1,2 or 5.

For solving this question we can just find the minimum number in the array. The final value of all the number will be [min(Array)-4, min(Array)] We can just iterate over all the 5 values, and for each value we can find the minimum number of moves to make all the elements to the chosen value. Finally take the minimum of all the 5 answers we get in each test case. That will be the result. Here is my C++ code -

#include<bits/stdc++.h>
using namespace std;

#define int long long int

signed main(){
    int t;
    cin>>t;
    while(t--){
        int n, res = INT_MAX, mini = INT_MAX, ans, temp;
        cin>>n;
        int A[n];
        for(int i=0;i<n;i++){
            cin>>A[i];
            mini = min(mini, A[i]);
        }
        for(int i=mini-4;i<=mini;i++){
            ans = 0;
            for(int j=0;j<n;j++){
                temp = A[j]-i;
                temp = temp/5+(temp%5)/2+(temp%5)%2;
                ans += temp;
            }
            res = min(ans, res);
        }
        cout<<res<<"\n";
    }

    return 0;
}

Answer 2

The approach that you found doesn't work for the set of element consisting of 1, 2, and 5. As you said, for 1, 5, 5 the approach results in 4 operations (for the "coin change"), for example:

1, 5, 5 -> 1, 3, 5 -> 1, 1, 5 -> 1, 1, 3 -> 1, 1, 1

For the purpose of equalizing all elements, increasing all but one element by 1, 2, or 5, is essentially the same as decreasing one element by the corresponding value (see this answer). If you view your problem this way, then it is equal to this problem.

The answer to the latter problem explains that it is not sufficient to only consider the differences between the minimum element and the non-minimum elements. You also have to consider the difference of all elements to the the minimum element - 1 and to the minimum element - 2. For 1, 5, 5 this results in, for example, the following operations:

1, 5, 5 -> 0, 5, 5 -> 0, 0, 5 -> 0, 0, 0

1, 5, 5 -> -1, 5, 5 -> -1, 0, 5 -> -1, -1, 5 -> -1, -1, 0 -> -1, -1, -1

As you can see, for your example, considering the difference between all elements and the minimum element - 1 gives the minimum number of operations needed to equalize all elements, which is 3.

You should adapt your code so that it reflects this approach.