C++ 12 ms O(n) 8 lines


  • 7
    V

    First. we determine the target dresses we should have in each machine (total dresses / # of machines), and return -1 if it's not an integer.

    We then go from left to right, tracking the running balance of dresses we need to move through each machine. If, for example, we have 5 extra dresses so far, and this machine has 2 extra dresses, we need to pass total 7 dresses through that machine (requires 7 steps). Also, we need to track the number of dresses we need to offload from a particular machine (machine[i] - target dresses). This number may be higher than the running balance if dresses are passed both ways, as shown in the example 2.

    Example 1: [1, 1, 6, 6, 1], total dresses: 15, target dresses: 3, maximum offload is 3 (6 - 3).
    Running balance:[-2][-4][ -1][ 2][ 0]
    Answer: max(3, abs(-4)) = 4.

    Example 2: [1, 1, 4, 8, 1], total dresses: 15, target dresses: 3, maximum offload is 5 (8 - 3).
    Running balance:[-2][-4][ -3][ 2][ 0]
    Answer: max(5, abs(-4)) = 5

    int findMinMoves(vector<int>& machines) {
        int totalDresses = 0, size = machines.size();
        for (auto i = 0; i < size; ++i) totalDresses += machines[i];
        if (totalDresses % size != 0) return -1;
        
        auto targetDresses = totalDresses / size, totalMoves = 0, ballance = 0;
        for (auto i = 0; i < size; ++i) {
            ballance += machines[i] - targetDresses;
            totalMoves = max(totalMoves, max(machines[i] - targetDresses, abs(ballance)));
        }
        return totalMoves;
    }
    

  • 0
    A

    Nice - definitely a bit simpler than my solution. I had a bit of trouble understanding the correctness of your max line so I separated out the cases a little bit. Hope this makes things clearer for others.

    
      int findMinMoves(vector<int>& M) {
          int n = M.size();
          if (n == 0) return 0;
          
          int s = 0;
          for (int d : M) s += d;
          
          if (s % n != 0) return -1;
          
          int target = s / n;
          int moves = 0;
          int balance = 0;
          
          for (int i = 0; i < n; i++) {
              // How much to send left from this machine?
              int left = 0;
              if (balance < 0) {
                  left = -balance;
                  moves = max(moves, left); 
              }
              
              balance += (M[i] - target);
              
              // If balance is positive, how much to send right?
              int right = 0;
              if (balance > 0) {
                  right = balance;
                  // We cannot send left and right at the same time so we have to
                  // send left/right separately.
                  moves = max(moves, left + right);
              }
          }
          
          return moves;
      }
    };
    

  • 0
    V

    @amaximov Correct, when balance changes from negative to positive, we need to sum dresses we send left and right. In this case, I figured, (left + right) equals (M[i] - target) - we need to send all extra dresses from this machine left and/or right.

    I was shooting for a concise code, so I did max(balance, M[i] - target). I agree It could make code harder to read, but folks here seem to like cryptic one-liners in Python, so I thought - what the heck.


Log in to reply
 

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