online advertising

Wednesday, November 9, 2016

LeetCode OJ - Minimum Moves to Equal Array Elements

Problem:

Please find the problem here.

Analysis: 

The trick here is that instead of thinking increasing $ n - 1 $ element, we can also think of it as decreasing one element. In fact, increasing $ n $ element all at once and then choose $ 1 $ to decrease. In terms of getting the element to equal each other, the increasing step is meaningless, we can ignore that.

Solution:

Following the thinking above, here is the example sequence:

[1, 2, 3] -> [2, 3, 3] -> [3, 4, 3] -> [4, 4, 4]

It can also be think as the decreasing sequence

[1, 2, 3] -> [1, 2, 2] -> [1, 2, 1] -> [1, 1, 1]

Now this is particularly enlightening, it just simply reduce every number to the minimum. Think about it, because all you could do is the decrement by 1, there is simply no better way, therefore the answer is simply the difference between every element with the minimum, or more conveniently, sum of all elements minus the minimum times the number of element.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/minimum-moves-to-equal-array-elements/

#include "LEET_MINIMUM_MOVES_TO_EQUAL_ARRAY_ELEMENTS.h"
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

namespace _LEET_MINIMUM_MOVES_TO_EQUAL_ARRAY_ELEMENTS
{
    class Solution
    {
    public:
        int minMoves(vector<int>& nums)
        {
            int m = ~(1 << 31);
            int s = 0;
            for (int i = 0; i < nums.size(); i++)
            {
                m = min(nums[i], m);
                s += nums[i];
            }
            return s - m * nums.size();
        }
    };
};

using namespace _LEET_MINIMUM_MOVES_TO_EQUAL_ARRAY_ELEMENTS;

int LEET_MINIMUM_MOVES_TO_EQUAL_ARRAY_ELEMENTS()
{
    Solution solution;
    int input_array[] = { 1, 2, 3 };
    vector<int> input(input_array, input_array + _countof(input_array));
    cout << solution.minMoves(input) << endl;
    return 0;
}

No comments :

Post a Comment