How to Get Minimum Moves to Equal Array Elements?

Given an array (non empty) of integers, find the number of minimum moves to make all elements equal. A move is to increment (n – 1) elements by one. For example, [1, 3] needs two moves to make all elements equal: [1, 3] – [2, 3] and [3, 3].

How to Move? Greedy Solution

The strategy of moves is to NOT pick the maximum value (Greedy Algorithm). Incrementing the maximum element is like going to the opposite direction e.g. [1, 4] needs 3 more moves to complete instead of [2, 3] which just needs 1 more move. It is also equivalent to decrementing the maximum element at each move. Therefore, we just need to count the number of moves for each element towards a global minimal.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int minMoves(vector<int>& nums) {
        int sum = 0;
        int v = INT_MAX;
        for (auto i: nums) {
            sum += i;
            v = min(i, v);
        }
        return sum - v * nums.size();
    }
};

class Solution {
public:
    int minMoves(vector<int>& nums) {
        int sum = 0;
        int v = INT_MAX;
        for (auto i: nums) {
            sum += i;
            v = min(i, v);
        }
        return sum - v * nums.size();
    }
};

C++ Syntax Sugar – Sum and Min

The above O(n) implementation is straightforward but you can also make it better by using the syntax sugar (or library to be more precise).

std::min_element

std::min_element returns the iterator of the minimal element. Get the value by dereferencing it.

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int minMoves(vector<int>& nums) {
        int min = *std::min_element(nums.begin(), nums.end());
        int s = 0;
        for (auto i: nums) {
            s += i - min;
        }
        return s;
    }
};

class Solution {
public:
    int minMoves(vector<int>& nums) {
        int min = *std::min_element(nums.begin(), nums.end());
        int s = 0;
        for (auto i: nums) {
            s += i - min;
        }
        return s;
    }
};

Using a standard numeric algorithm library

The numeric allows you to sum the elements in a vector.

1
2
3
4
5
6
7
8
9
10

#include <numeric>
 
class Solution {
public:
    int minMoves(vector<int>& nums) {
        int min = *std::min_element(nums.begin(), nums.end());
        int sum = std::accumulate(nums.begin(), nums.end(), 0);
        return sum - min * nums.size();
    }
};

#include <numeric>

class Solution {
public:
    int minMoves(vector<int>& nums) {
        int min = *std::min_element(nums.begin(), nums.end());
        int sum = std::accumulate(nums.begin(), nums.end(), 0);
        return sum - min * nums.size();
    }
};

In fact, there are quite a few ways to sum the elements in a C++ vector. Pick your favorite!

1
2
3
4
5
6
7
8

// Classic for loop:
for (auto it = nums.begin(); it != nums.end(); ++it)
    sum += *it;
 
// C++11 and higher
std::for_each(nums.begin(), nums.end(), [&] (int n) {
    sum += n;
});

// Classic for loop:
for (auto it = nums.begin(); it != nums.end(); ++it)
    sum += *it;

// C++11 and higher
std::for_each(nums.begin(), nums.end(), [&] (int n) {
    sum += n;
});

–EOF (The Ultimate Computing & Technology Blog) —