c++ 3ms solution with explanations


  • 0
    D

    For every element in the array, we consider two operations, receive and send.
    Considered that an element can receive 0, 1, 2 within a move, but only can send 0, 1 within a move. So, we only need to calculate the most send times among all elements.
    If the final average element is ave, for element a[i], it send x[i] to a[i-1], we can get a[i] - x[i-1] + x[i] = ave, we know x[0] = 0, so we can get every x[i].
    In the below cod, pre indicate x[i], next indicate x[i+1], the actual send times for a[i] is max(pre, 0) - min(0, next). Find the max one.

    int findMinMoves(vector<int>& machines) {
        int sum = 0;
        for(int i = 0;i < machines.size();i ++)
            sum += machines[i];
        if(sum % machines.size() != 0)
            return -1;
        int res = 0;
        int pre = 0, ave = sum / machines.size();
        for(int i = 0;i < machines.size();i ++) {
            int next = ave + pre - machines[i];
            int cnt = max(pre, 0) - min(0, next);
            
            pre = next;
            res = max(cnt, res);
        }
        return res;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.