Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/453.html

453. Minimum Moves to Equal Array Elements

Level

Easy

Description

Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 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

Incrementing n - 1 elements by 1 is equivalent to incrementing all elements by 1 and decrementing one element by 1. Since incrementing all elements by 1 doesn’t change whether the elements are equal, the procedure is equivalent to decrementing only one element by 1.

Sort the array, and since each element can only be decremented, the only way to make all elements equal is to decrement all elements to the smallest element, and thus the minimum moves can be calculated.

  • class Solution {
        public int minMoves(int[] nums) {
            Arrays.sort(nums);
            int min = nums[0];
            int moves = 0;
            int length = nums.length;
            for (int i = 0; i < length; i++)
                moves += nums[i] - min;
            return moves;
        }
    }
    
  • class Solution:
        def minMoves(self, nums: List[int]) -> int:
            return sum(nums) - min(nums) * len(nums)
    
    ############
    
    class Solution(object):
      def minMoves(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sum(nums) - len(nums) * min(nums)
    
    
  • class Solution {
    public:
        int minMoves(vector<int>& nums) {
            int s = 0;
            int mi = INT_MAX;
            for (int num : nums) {
                s += num;
                mi = min(mi, num);
            }
            return s - mi * nums.size();
        }
    };
    
  • func minMoves(nums []int) int {
    	mi := math.MaxInt32
    	s := 0
    	for _, num := range nums {
    		s += num
    		if num < mi {
    			mi = num
    		}
    	}
    	return s - mi*len(nums)
    
    }
    
  • function minMoves(nums: number[]): number {
        let mi = 1 << 30;
        let s = 0;
        for (const x of nums) {
            s += x;
            mi = Math.min(mi, x);
        }
        return s - mi * nums.length;
    }
    
    

All Problems

All Solutions