Problem Description
Given an integer n, we have an array arr of length n where each element is defined by arr[i] = 2 * i + 1. In one operation, you can choose two indices x and y and subtract 1 from arr[x] while adding 1 to arr[y]. The goal is to equalize all elements in the array using the minimum number of such operations. It is guaranteed that this is always possible.
Key Insights
- The array is symmetric with values: [1, 3, 5, ..., (2*n - 1)].
- The target value for all elements is the median of the array.
- The operations essentially balance out the differences between the smaller and larger elements.
- A mathematical simplification shows that the minimum number of operations equals the sum of differences for the first half of the array.
- Using a closed-form formula, the answer can be computed directly as n^2 // 4.
Space and Time Complexity
Time Complexity: O(n) if summing over half the array, but with the closed-form formula it is O(1).
Space Complexity: O(1).
Solution
The key observation is that because the array is symmetric and the operations are reversible, the best strategy is to equalize elements by transferring units from the larger half to the smaller half of the array, with the target being the median value. If we denote the median as m, we only need to compute the total difference for the lower half:
For each element in the first half, the difference with m is (m - arr[i]). Summing these differences will yield the total minimum operations required. After simplifying the sum, the formula reduces to n^2 // 4.
We use simple arithmetic operations without any additional data structures. This provides both clarity and efficiency.