You are given an array of N integers. In one step, you can increment or decrement an element by 1. Find the minimum number of steps required to make all elements of the array equal.
def min_steps_to_equal(arr):
"""
Calculates the minimum steps to make all elements of an array equal.
Args:
arr: An array of N integers.
Returns:
The minimum number of steps required.
"""
arr.sort() # Sort the array in ascending order.
median = arr[len(arr) // 2] # Find the median element.
steps = 0
for num in arr:
steps += abs(num - median) # Calculate the absolute difference between each element and the median.
return steps
# Example usage:
arr1 = [2, 5, 1, 8, 3]
print(f"Minimum steps for arr1: {min_steps_to_equal(arr1)}") # Output: 11
arr2 = [1, 2, 3, 4, 5]
print(f"Minimum steps for arr2: {min_steps_to_equal(arr2)}") # Output: 6
arr3 = [1, 1, 1, 1, 1]
print(f"Minimum steps for arr3: {min_steps_to_equal(arr3)}") # Output: 0
arr4 = [2, 2, 4, 4]
print(f"Minimum steps for arr4: {min_steps_to_equal(arr4)}") # Output: 4
arr5 = [-2, -1, 0, 1, 2]
print(f"Minimum steps for arr5: {min_steps_to_equal(arr5)}") # Output: 6
arr6 = [1, 6, 2, 3, 4, 5, 7]
print(f"Minimum steps for arr6: {min_steps_to_equal(arr6)}") # Output: 12
Explanation and Rationale:
The key insight to solving this problem efficiently is that the median of the sorted array is the optimal value to which all other elements should be made equal. Here’s why:
Sorting: We first sort the array. This allows us to easily find the median and also makes the subsequent calculations more straightforward.
Median as the Target: The median minimizes the sum of absolute differences. Intuitively, if you choose a value smaller than the median, you’d have to make larger increments for the elements greater than the median than the decrements for elements smaller than the median. The opposite is true if you select a value larger than the median. The median balances these increments and decrements.
Calculating Steps: We iterate through the sorted array and calculate the absolute difference between each element and the median. The sum of these absolute differences gives us the minimum number of steps required.
Time Complexity: O(n log n) due to the sorting step. The rest of the operations are O(n).
Space Complexity: O(1) if we sort the array in place. Otherwise, it might be O(n) depending on the sorting algorithm used.