Skip to content

3736. Minimum Moves to Equal Array Elements III

Description

You are given an integer array nums.

In one move, you may increase the value of any single element nums[i] by 1.

Return the minimum total number of moves required so that all elements in nums become equal.

 

Example 1:

Input: nums = [2,1,3]

Output: 3

Explanation:

To make all elements equal:

  • Increase nums[0] = 2 by 1 to make it 3.
  • Increase nums[1] = 1 by 1 to make it 2.
  • Increase nums[1] = 2 by 1 to make it 3.

Now, all elements of nums are equal to 3. The minimum total moves is 3.

Example 2:

Input: nums = [4,4,5]

Output: 2

Explanation:

To make all elements equal:

  • Increase nums[0] = 4 by 1 to make it 5.
  • Increase nums[1] = 4 by 1 to make it 5.

Now, all elements of nums are equal to 5. The minimum total moves is 2.

 

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

Solutions

Solution 1: Calculate Sum and Maximum Value

This problem requires making all elements in the array equal, with each operation only able to increase a single element by 1. To minimize the number of operations, we should make all elements equal to the maximum value in the array.

Therefore, we can first calculate the maximum value \(\textit{mx}\) and the sum of array elements \(\textit{s}\). The number of operations required to make all elements equal to \(\textit{mx}\) is \(\textit{mx} \times n - \textit{s}\), where \(n\) is the length of the array.

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

1
2
3
4
5
6
class Solution:
    def minMoves(self, nums: List[int]) -> int:
        n = len(nums)
        mx = max(nums)
        s = sum(nums)
        return mx * n - s

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int minMoves(int[] nums) {
        int n = nums.length;
        int mx = 0;
        int s = 0;
        for (int x : nums) {
            mx = Math.max(mx, x);
            s += x;
        }
        return mx * n - s;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int minMoves(vector<int>& nums) {
        int n = nums.size();
        int mx = 0;
        int s = 0;
        for (int x : nums) {
            mx = max(mx, x);
            s += x;
        }
        return mx * n - s;
    }
};

1
2
3
4
5
6
7
8
func minMoves(nums []int) int {
    mx, s := 0, 0
    for _, x := range nums {
        mx = max(mx, x)
        s += x
    }
    return mx*len(nums) - s
}

1
2
3
4
5
6
function minMoves(nums: number[]): number {
    const n = nums.length;
    const mx = Math.max(...nums);
    const s = nums.reduce((a, b) => a + b, 0);
    return mx * n - s;
}

Comments