Minimum number of moves to equal array elements – LeetCode Solution [Medium]

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment n - 1 elements of the array by 1.

Problem Statement
Minimum Moves to Equal Array Elements

Example 1:

Input: nums = [1,2,3]
Output: 3
Explanation:
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

Minimum number of moves to equal array elements solution

Approach

The idea is to understand that increasing all array elements by 1 except one element is same as decreasing only one element by 1 to equalise all elements.
Consider above example:

nums = [1, 2, 3]
1. [1, 2-1, 3] = [1, 1, 3]
2. [1, 1, 3-1] = [1, 1, 2]
3. [1, 1, 2-1] = [1, 1, 1]
Hence, 3 moves

Now this could also be stated as follows:

moves = 3-1 + 2-1 + 1-1
[Hence moves = Difference between each element of array and minimum number in array]
      = 3 + 2 + 1 - 1 - 1 - 1
      = Sum[nums] - Size[nums] * Minimum[nums]

Time complexity: O(n), n is the number of elements in array.

Code Implementation

//
//  main.cpp
//  Number of moves
//
//  Created by Himanshu on 19/09/21.
//


#include <iostream>
#include <vector>
using namespace std;
#define MAX 100


int solve (vector<int> nums) {
    int sum = 0, minElement = INT_MAX, n = (int) nums.size();
    for (int i=0; i<n; i++) {
        minElement = min(minElement,  nums[i]);
        sum += nums[i];
    }
    
    return (sum - (n*minElement));
}

int main(int argc, const char * argv[]) {
    vector<int> nums = {1, 2, 3};

    printf("Number of moves to equalise array elements: %d\n", solve( nums));

    return 0;
}

Output

Number of moves to equalise array elements: 3

Here’s a working example: Ideone