Algorithm Solution: Minimum Moves Equal Array Elements
This algorithm is part of my goals this year.
Given an integer array
n, return the minimum number of moves required to make all array elements equal. In one move, you can increment
n - 1elements of the array by
Complete problem description can be found here: https://leetcode.com/problems/minimum-moves-to-equal-array-elements/
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
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
[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 = 2
2 - 1 = 1
1 - 1 = 0
Now we sum the difference:
2 + 1 + 0 = 3, so we got here! 3 moves!!
Hi there! Are you enjoying what you're reading? If you do, you can be the first to know when I post cool stuff!