CODEWITHSUNDEEP
c++algorithm
Roni Belkin
Roni Belkin

Reputation: 1

Minimum Moves to Equal Array Elements help to understand the solution

I saw a solution that I could not understand what stand behind the solution and I would like to understand why the solution is correct (what stand behind the idea), The problem is "Minimum Moves to Equal Array Elements". The solution that I saw is:

 int minMoves(vector<int>& nums) {
    long minimum = nums[0]; 
    long sum = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        sum += nums[i];
        if (nums[i] < minimum)
            minimum = nums[i];
    }
    return sum - minimum * nums.size();
}

I didn't understand why the sum of elements subtraction the minimal element multiply the length of array gives the solution of the problem ?

edit: this is the explanation of the problem: 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]

Upvotes: 0

Views: 996

Answers (2)

larticho
larticho

Reputation: 169

From what I understand, your problem is : you have an array of integer, your only move is to decrease one element, what is the minimal number of move you have to do to have an array with all the elements equal.

A first idea for this problem would be to first look for the minimum of the array, and then add the diffence between each element and the minimum.

So here, with minthe minimum of the array, you want to calculate the sum of nums[i]-min for i between 0 and the size of your array. But it is the same as calculate the sum of nums[i] (the sum of the elements of your array), then the sum of min, and then do the difference.

min being constant, your sum of min is the same as min*nums.size().

In the answer you gave, both the minimum and the sum of the array are calculated in the same for loop. After that, it gives you the difference I explained before, which is your answer.

Upvotes: 0

Saeed Amiri
Saeed Amiri

Reputation: 22555

Per my understanding from the question as @larticho explained in the comments, the only operator given is minus. Therefore, what you cannot do is that you cannot change the value of minimum (or if you change it, it is pointless and it causes only extra moves). Therefore what you have to do is to reduce the size of every other element to be equal as a minimum. Therefore, the total number of moves equals the distance of all elements together from a minimum.

I.e. ∑i=1..n (xi - min), if you put it into two separate summations, it will be ∑i=1..n xi - ∑i=1..n min, which is equal to ∑ xi - n * min as written in the code.

Upvotes: 1

Related Questions