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.
1class Solution {
2 public int findMinMoves(int[] machines) {
3 int totalDresses = 0;
4 for (int dresses : machines) {
5 totalDresses += dresses;
6 }
7 int n = machines.length;
8 if (totalDresses % n != 0) return -1;
9 int target = totalDresses / n;
10 int maxMoves = 0, balance = 0;
11 for (int dresses : machines) {
12 int diff = dresses - target;
13 balance += diff;
14 maxMoves = Math.max(maxMoves, Math.max(Math.abs(balance), diff));
15 }
16 return maxMoves;
17 }
18
19 public static void main(String[] args) {
20 Solution sol = new Solution();
21 int[] machines = {1, 0, 5};
22 System.out.println(sol.findMinMoves(machines)); // Output: 3
23 }
24}In this Java implementation, the process of balancing the loading across machines is carried out by adjusting the load differences from the target and maintaining a running balance.