← leetcode

Minimum Moves to Equal Array Elements

· Medium

LeetCode problem 453

the trick to the question is realising that incrementing n-1 elements of the array by 1 achieves the same effect on the gaps between the values as decrementing by 1 the one element that you didn't increment.

an example of this would be:

# incrementing n-1 values:
1 1 3 5 7 => 2 2 4 6 7

# decrementing 1 value:
1 1 3 5 7 => 1 1 3 5 6

where you can see that the differences between the values stay the same.

therefore, we can simply add up the number of decrement operations we need to make for all the values to be equal to the minimum value, since the minimum value never needs to go down.

code link to code

class Solution {
public:
    int minMoves(vector<int>& nums) {
        int ans{0};
        int mn = INT32_MAX;
        for (int num : nums) {
            ans += num;
            mn = min(num, mn);
        }
        return ans - static_cast<int>(nums.size()) * mn;
    }
};

complexity link to complexity

  • Time: O(n)
  • Space: O(1)

time taken link to time taken

  • DNF
    • i gave up after an hour... the solution is not that hard...