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 <stdio.h>
2#include <stdlib.h>
3
4int findMinMoves(int* machines, int machinesSize) {
5 int totalDresses = 0;
6 for (int i = 0; i < machinesSize; ++i) {
7 totalDresses += machines[i];
8 }
9 if (totalDresses % machinesSize != 0) return -1;
10
11 int target = totalDresses / machinesSize;
12 int maxMoves = 0, balance = 0;
13 for (int i = 0; i < machinesSize; ++i) {
14 int diff = machines[i] - target;
15 balance += diff;
16 maxMoves = fmax(maxMoves, fmax(abs(balance), diff));
17 }
18 return maxMoves;
19}
20
21int main() {
22 int machines[] = {1, 0, 5};
23 int result = findMinMoves(machines, 3);
24 printf("%d\n", result); // Output: 3
25 return 0;
26}This implementation starts by calculating the total number of dresses. If it isn't divisible by the number of machines, we return -1. Next, we calculate the difference between each machine's load and the average load, keeping a running balance, and determine the maximum number of moves by considering both the load difference and the accumulative balance, which is necessary due to passing dresses through intermediate machines.