Sponsored
Sponsored
The greedy approach involves determining the imbalance of dresses between adjacent machines and making moves to balance it. We find the maximum number of dresses that need to be moved either into or out of any machine to balance the system.
If it's impossible to balance the dresses equally among all machines (i.e., the total number of dresses is not divisible by the number of machines), the solution is -1.
Time Complexity: O(n), where n is the number of machines.
Space Complexity: O(1), since we use a constant amount of extra space.
1#include <vector>
2#include <cmath>
3#include <iostream>
4
5class Solution {
6public:
7 int findMinMoves(std::vector<int>& machines) {
8 int totalDresses = 0;
9 for (int dresses : machines) {
10 totalDresses += dresses;
11 }
12 int n = machines.size();
13 if (totalDresses % n != 0) return -1;
14 int target = totalDresses / n;
15 int maxMoves = 0, balance = 0;
16 for (int dresses : machines) {
17 int diff = dresses - target;
18 balance += diff;
19 maxMoves = std::max(maxMoves, std::max(std::abs(balance), diff));
20 }
21 return maxMoves;
22 }
23};
24
25int main() {
26 Solution sol;
27 std::vector<int> machines = {1, 0, 5};
28 std::cout << sol.findMinMoves(machines) << std::endl; // Output: 3
29 return 0;
30}This C++ solution is similar to the C solution, using a vector to represent the machines. We determine the maximum number of moves required to balance the machines based on the current balance and the difference from the target load.