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; }