Algorithm Solution: Minimum Moves Equal Array Elements
This algorithm is part of my goals this year.
Given an integer arraynumsof sizen, return the minimum number of moves required to make all array elements equal. In one move, you can incrementn - 1elements of the array by1.
Complete problem description can be found here: https://leetcode.com/problems/minimum-moves-to-equal-array-elements/
Solution
class Solution:
def minMoves(self, nums: list[int]) -> int:
least = min(nums)
total_dif = 0
for n in nums:
total_dif += n - least
return total_dif
Solution().minMoves([1,2,3])Explanation
I'm willing to show my reasoning because it took me a long time to really understand it.
So, first things first, let's consider the same example: an array with [1, 2, 3]. Cool.
The problem description tells you that you should count how much moves (or sums) to make all values equal, always excluding one. So, we can think reversely by saying we could count how much moves (or subtracts) to make all values equal, only considering one.
So, instead of:
[1,2,3] -> [2,3,3] -> [3,3,4] -> [4,4,4] = 3 moves
We do:
[1,2,3] -> [1,2,2] -> [1,1,2] -> [1,1,1] = 3 moves
The logic is the same:
- Decrease 1 over Sum every but one.
Nice, with that being clear it gets easier. We need to find out how much subtracts should happen, and it always will be related to the minimum number. So, in our case, if it's 1 (one), then we need to find out how much different to subtract. So:
3 - 1 = 22 - 1 = 11 - 1 = 0
Now we sum the difference: 2 + 1 + 0 = 3, so we got here! 3 moves!!
