To solve this problem, we need to determine the minimum number of operations required to make all elements in an array equal. Each operation allows incrementing or decrementing an element by 1. The key insight here is that the minimal sum of absolute differences (which corresponds to the number of operations) is achieved when we choose the median of the array as the target value.

Approach

1. Sort the Array: Sorting helps in easily finding the median.
2. Find the Median: The median of a sorted array is the middle element. For even-length arrays, either of the two middle elements works (since the sum of absolute differences will be the same).
3. Calculate Operations: Compute the sum of absolute differences between each element and the median. This sum gives the minimal number of operations needed.

Solution Code

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
median = arr[n // 2]
total_operations = sum(abs(x - median) for x in arr)
print(total_operations)

Explanation

1. Sorting: Sorting the array allows us to quickly access the median. For example, if the array is [1, 3, 5, 7], sorting gives [1, 3, 5, 7], and the median can be either 3 or 5 (both yield the same sum of differences).
2. Median Selection: The median minimizes the sum of absolute deviations. This is because the median is the middle value, so half the elements are on either side, leading to the smallest total distance.
3. Sum Calculation: The sum of absolute differences between each element and the median gives the total number of operations needed to make all elements equal to the median.

This approach efficiently computes the result with a time complexity dominated by the sorting step, which is (O(n \log n)), making it suitable for large input sizes. The space complexity is (O(1)) (excluding input storage), as we only need to store the median and the sum.

Example: For input array [1, 2, 3, 4, 5], the median is 3. The sum of differences is (|1-3| + |2-3| + |3-3| + |4-3| + |5-3| = 2+1+0+1+2 =6), which is the minimal number of operations.

This solution is optimal and handles all edge cases (e.g., single element, all elements the same, even/odd length arrays).)

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