Thursday, May 23, 2019

Leetcode 453: Minimum Moves to Equal Array Elements

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:
First, the method of decreasing 1 instead of adding 1 for n-1 elements is brilliant. But, when I was doing the contest, I was dumb, so dumb to think outside the box. And this is how I tackled it using just math logic.
First, traverse the array, get the sum and the minimum value. If every element is equal, then min*(len) should equal to sum. This part is easy to understand. So, if they are not equal, what should we do? we should keep adding 1 to the array for k times until min*(len)==sum. Then we have:
len*(min+k)=sum+k*(len-1). ==> k=sum-min*len;

Code (Java):
/*
 * @lc app=leetcode id=453 lang=java
 *
 * [453] Minimum Moves to Equal Array Elements
 */
class Solution {
    public int minMoves(int[] nums) {
        if (nums == null || nums.length  <= 1) {
            return 0;
        }

        int min = nums[0];
        long sum = 0;
        for (int num : nums) {
            sum += num;
            min = Math.min(min, num);
        }

        return (int)(sum - nums.length * min);
    }
}



No comments:

Post a Comment