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 def findMinMoves(self, machines):
3 totalDresses = sum(machines)
4 n = len(machines)
5 if totalDresses % n != 0:
6 return -1
7 target = totalDresses // n
8 max_moves = balance = 0
9 for dresses in machines:
10 diff = dresses - target
11 balance += diff
12 max_moves = max(max_moves, abs(balance), diff)
13 return max_moves
14
15sol = Solution()
16machines = [1, 0, 5]
17print(sol.findMinMoves(machines)) # Output: 3The Python solution calculates the total number of dresses and the target evenly distributed load, then determines the maximum shifts required by tracking the cumulative balance and direct moves needed per machine.