 احمد - 2 years ago 319
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;
}

}
}
`````` Omid N

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;
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);