احمد - 10 months ago 179

C++ Question

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 Source

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;
}
```