To solve this problem, we need to determine the minimum number of operations required to make all elements of an array equal. The allowed operation is transferring 1 unit from one element to another, which keeps the total sum of the array unchanged.
Approach
- Check Feasibility: Since the sum of the array remains constant, all elements can only be made equal if the total sum is divisible by the number of elements. If not, it's impossible to make all elements equal, so return -1.
- Target Value: If feasible, the target value for each element is the total sum divided by the number of elements.
- Calculate Operations: The number of operations needed is the sum of the excess values over the target (since each excess unit needs to be moved to an element that is below the target).
Solution Code
def min_operations(nums):
total = sum(nums)
n = len(nums)
if total % n != 0:
return -1
target = total // n
operations = 0
for num in nums:
if num > target:
operations += num - target
return operations
Explanation
- Feasibility Check: The sum of the array must be divisible by the number of elements to ensure a valid target value (an integer).
- Target Calculation: The target value is the average of the array elements, which is the sum divided by the count of elements.
- Operations Calculation: For each element greater than the target, the excess value (element - target) contributes to the number of operations. Each excess unit needs to be moved once, so summing these excess values gives the total number of operations.
This approach runs in O(n) time complexity (since we traverse the array once) and uses O(1) additional space, making it optimal for the problem constraints.
Answer: The function min_operations returns the minimum number of operations or -1 if it's impossible. For example, if the input array is [1,2,3], the output is 1. If the input is [1,2], the output is -1. If the input is [1,1,3,3], the output is 2.
The final answer is the code provided above.
def min_operations(nums):
total = sum(nums)
n = len(nums)
if total % n != 0:
return -1
target = total // n
operations = 0
for num in nums:
if num > target:
operations += num - target
return operations


作者声明:本文包含人工智能生成内容。