احمد احمد - 1 month ago 78
C++ Question

Minimum Moves to Equal Array Elements

Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.

Example:

Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
Discuss

I tried to brute force it, but I couldn't come with a correct algorithm, the loop invariants are incorrect. Would someone fix it with explanation so that I can improve my algorithms skills ?

bool checkEquality(vector<int> &num)
{

for (int j = 1; j < num.size(); j++)
{
if (num[j] != num[j - 1])
{
return false;
}
}
return true;
}


int main() {

vector<int> num = { 1, 2,3 };

int numMoves = num.size() - 1;
int prev = 0;
int j = 0;
while(!checkEquality(num))
{
for (int i = prev; i < num.size(); i++)
{
for ( j = i; j < numMoves; j++)
{
num[j]++;

}
if (i == num.size())
{
prev = j;
j = 0;

}
else
prev = 0;
}

}
}

Answer

You can see the problem as decreasing an element instead of increasing the others with one.

now the problem is a lot more simple. you just need to add every element until it reaches the maximum element in the array. I will solve it as below:

int findMax(vector<int> &num)
{
    int maximum=num[0];
    for(int i=1;i<num.size();i++)
    {
        if(maximum<num[i])
            maximum=num[i];
    }
    return maximum;
}

int main()
{
    vector<int> num;
    num.push_back(1);
    num.push_back(2);
    num.push_back(3);

    int max_val=findMax(num);

    int answer=0;
    for(int i=0;i<num.size();i++)
    {
        answer+=max_val-num[i];
    }
    cout<<answer<<endl;

}