Watch 10 video solutions for Minimum Operations to Make Array Equal, a medium level problem involving Math. This walkthrough by Algorithms Made Easy has 25,089 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You have an array arr of length n where arr[i] = (2 * i) + 1 for all valid values of i (i.e., 0 <= i < n).
In one operation, you can select two indices x and y where 0 <= x, y < n and subtract 1 from arr[x] and add 1 to arr[y] (i.e., perform arr[x] -=1 and arr[y] += 1). The goal is to make all the elements of the array equal. It is guaranteed that all the elements of the array can be made equal using some operations.
Given an integer n, the length of the array, return the minimum number of operations needed to make all the elements of arr equal.
Example 1:
Input: n = 3 Output: 2 Explanation: arr = [1, 3, 5] First operation choose x = 2 and y = 0, this leads arr to be [2, 3, 4] In the second operation choose x = 2 and y = 0 again, thus arr = [3, 3, 3].
Example 2:
Input: n = 6 Output: 9
Constraints:
1 <= n <= 104Problem Overview: You start with an array of size n where arr[i] = 2*i + 1. In one operation you choose two indices and decrease one value by 1 while increasing the other by 1. The goal is to make every element equal using the minimum number of operations.
Approach 1: Brute Force Simulation (Inefficient but Useful for Understanding) (Time: O(n^2), Space: O(1))
This approach literally simulates the balancing process. Generate the array [1, 3, 5, ..., 2n-1], then repeatedly move units from larger elements to smaller ones until every value becomes the same. Conceptually, you push values toward the middle by transferring 1 unit from the right side of the array to the left side. Each transfer counts as one operation.
The simulation works because the final value must be the average of the array, which is exactly n. You keep adjusting pairs until both sides meet this target. Although easy to reason about, it becomes slow because each imbalance may require multiple step-by-step transfers. With nested adjustments across elements, the time complexity grows to O(n^2). This method is mostly useful for understanding the mechanics of the operation rather than for efficient implementation.
Approach 2: Balanced Operations Towards Median (Math Insight) (Time: O(n) or O(1), Space: O(1))
The array is already symmetric: [1, 3, 5, ..., 2n-1]. The target value for every element must be the mean, which equals n. Instead of simulating operations, count how far elements on the left side are below this value. Each unit of deficit requires exactly one operation transferred from the right side.
For the first half of the array, compute how much each element needs to increase to reach n. For index i, the value is 2*i + 1, so the deficit is n - (2*i + 1). Summing these deficits gives the exact number of operations needed. Because the array is symmetric, the right side automatically provides the required decreases.
This observation leads to a clean mathematical formula. The total operations simplify to floor(n^2 / 4). You can either compute it directly in O(1) time or iterate through half the array in O(n). The solution relies purely on math reasoning and the structure of the array, avoiding any actual simulation.
Recommended for interviews: Interviewers expect the mathematical balancing insight. Starting with the brute force explanation shows you understand the mechanics of the operation, but recognizing the symmetry and reducing it to a formula demonstrates strong problem-solving and mathematical optimization. The optimal implementation runs in constant time and uses no extra memory.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2) | O(1) | Learning the mechanics of balancing operations step by step |
| Balanced Operations Towards Median (Math) | O(n) or O(1) | O(1) | Optimal interview solution using symmetry and mathematical formula |