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.
1using System;
2
3public class Solution {
4 public int FindMinMoves(int[] machines) {
5 int totalDresses = 0;
6 foreach (int dresses in machines) {
7 totalDresses += dresses;
8 }
9 int n = machines.Length;
10 if (totalDresses % n != 0) return -1;
11 int target = totalDresses / n;
12 int maxMoves = 0, balance = 0;
13 foreach (int dresses in machines) {
14 int diff = dresses - target;
15 balance += diff;
16 maxMoves = Math.Max(maxMoves, Math.Max(Math.Abs(balance), diff));
17 }
18 return maxMoves;
19 }
20
21 public static void Main(string[] args) {
22 var sol = new Solution();
23 int[] machines = {1, 0, 5};
24 Console.WriteLine(sol.FindMinMoves(machines)); // Output: 3
25 }
26}The C# solution is structured similarly to other languages, leveraging the balance between machines and tracking the maximum imbalance that needs correcting to reach an even distribution of dresses.