Algorithm Solution: Minimum Moves Equal Array Elements

gui commited 3 years ago · algorithms 🐍 Python interactive

This algorithm is part of my goals this year.


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.

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:

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:

Now we sum the difference: 2 + 1 + 0 = 3, so we got here! 3 moves!!

  • LinkedIn
  • Tumblr
  • Reddit
  • Google+
  • Pinterest
  • Pocket
x
+
def foo() -> str: return "Welcome to Gui Commits" foo()