453.Minimum Moves to Equal Array Elements

Tags: [math]

Link: https://leetcode.com/problems/minimum-moves-to-equal-array-elements/?tab=Description

Given anon-emptyinteger array of sizen, find the minimum number of moves required to make all array elements equal, where a move is incrementingn- 1 elements by 1.

Example:

Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

Solution: math

class Solution(object):
    def minMoves(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        return sum(nums) - len(nums) * min(nums)

Revelation:

• Increasing 1 on all the remaining elements is equal to that subtracting 1 from one element.
• initial_sum - final_sum = 1 * num_of_moves
• Because we only can do subtracting, and we want to minimize the number of moves, so the final equal elements should be the min value of the current array. So the final_sum = min(arr) * len(arr).

Note:

• Time complexity = O(n). n is the number of elements of the given numbers.