Leetcode 453. Minimum Moves to Equal Array Elements

Problem Explanation

In this task, we're given an array of integers, and the goal is to make all elements in this array equal by performing a certain number of moves. For each move, we increment all elements in the array by 1 except for one element. The task is to find the minimum number of these "moves" needed to make all elements equal.

Let's consider the example [1,2,3]:

1. In the first move, we can increment the first and the second elements, the array becomes [2,3,3].
2. In the second move, we can increment the first and the third elements, the array becomes [3,4,3].
3. In the third move, we can increment the second and the third elements, the array becomes [4,4,4].

Hence, we required 3 moves to make all elements equal.

The trick to solve this problem efficiently is to instead of adding 1 to n - 1 elements, subtract 1 from a single element, because it achieves the equivalent effect.

With this strategy, the plan becomes to subtract each number until it equals the minimum number in the array.

---

Solution Approach

To get minimum number of moves, we need to perform the operations on the maximum elements till all of them become equal to the minimum element. This could be done in one pass. We get minimum element min_num of array and add difference of every element and min_num to moves.

Python Solution

1
2python
3class Solution:
4    def minMoves(self, nums):
5        
6        min_num = min(nums)
7        moves = 0
8
9        for num in nums:
10            moves += num - min_num
11            
12        return moves

In this Python solution, we first find the minimum number in the array nums. Then for each number in array, we add the difference between that number and the minimum number to the total number of moves.

Java Solution

1
2java
3public class Solution {
4    public int minMoves(int[] nums) {
5        int min_num = Integer.MAX_VALUE;
6        int moves = 0;
7        
8        for(int num : nums) {
9            min_num = Math.min(min_num, num);
10        }
11        
12        for(int num : nums) {
13            moves += num - min_num;
14        }
15        
16        return moves;
17    }
18}

In this Java solution, the approach is the same but Java doesn't have built in min function for array like Python so we are using a loop to find the min_num.

JavaScript Solution

1
2javascript
3class Solution {
4    minMoves(nums) {
5        let min_num = Math.min(...nums);
6        let moves = 0;
7
8        for(let num of nums) {
9            moves += num - min_num;
10        }
11
12        return moves;
13    }
14}

This JavaScript solution is the same as the Python solution. It uses the Math.min function to find the minimum number in the nums array.

C++ Solution

1
2cpp
3class Solution {
4public:
5    int minMoves(vector<int>& nums) {
6        auto min_num = *min_element(begin(nums), end(nums));
7        int moves = 0;
8        
9        for(auto num : nums) {
10            moves += num - min_num;
11        }
12        
13        return moves;
14    }
15};

In the C++ solution, we use the min_element function from the algorithm library to find the minimum number.

C# Solution

1
2csh
3public class Solution {
4    public int minMoves(int[] nums) {
5        int min_num = nums.Min();
6        int moves = 0;
7        
8        foreach(int num in nums) {
9            moves += num - min_num;
10        }
11        
12        return moves;
13    }
14}

In this C# solution, the approach is similar to the previous solutions. It uses LINQ's Min() method to find the smallest number in the array nums and then calculates total moves.## Ruby Solution

1
2ruby
3class Solution
4  def min_moves(nums)
5    min_num = nums.min
6    moves = 0
7
8    nums.each { |num| moves += num - min_num }
9
10    moves
11  end
12end

The Ruby solution uses the min method to find the smallest number in the nums array. Then, for each number in array, all the numbers in the array are subtracted from the minimum number, and this difference is added up to calculate the total number of moves.

Conclusion

The same logic has been applied in all these programming languages: Python, Java, JavaScript, C#, C++, and Ruby for solving the given problem. The key idea is to find the minimum element in the array, subtract each number of the array with this minimum number and accumulate these differences as the total required moves. By doing so, the approach gives the minimum moves required to equalize all elements in the array.

The time complexity is linear, O(n), because every step's complexity is O(n): finding the minimum of the array and computing the total moves.

Thus, the given problem can be solved effectively and efficiently using this approach.