Minimum Operations to Make Array Equal solution and explanation
9 more videos on this problem
Minimum Operations to Make Array Equal | Leetcode - 1551Algorithms Made Easy · 6:02 · 25K views
LeetCode 1551. Minimum Operations to Make Array Equal - Interview Prep Ep 91Fisher Coder · 9:35 · 8K views
Minimum Operations to Make Array Equal | LeetCode 1551 | Theory + Python + JavaSai Anish Malla · 13:53 · 2K views
Leetcode - Minimum Operations to Make Array Equal (Python)Timothy H Chang · 5:50 · 1K views
1551. Minimum Operations to Make Array Equal | Leetcode Medium |O (N) & O (1) time discussedChhavi Bansal · 16:40 · 1K views
Minimum Operations to Make Array Equal | LeetCode 1551 | Coders CampCoders Camp · 7:20 · 1K views
Minimum Operations to Make Array Equal | O(1) Space | 1551 LeetCode | LeetCode Explore | Day 06CodeWithSunny · 11:20 · 1K views
Minimum Operations to Make Array Equal | Leetcode 1551 | Live coding session | April 6 | ExploreCoding Decoded · 10:15 · 653 views
1551. Minimum Operations to Make Array Equal (Leetcode Medium)Programming Live with Larry · 5:06 · 411 views
Daily Leetcode #371: Apr 06, 2021 - 1551. Minimum Operations to Make Array EqualProgramming Live with Larry · 8:26 · 185 views
The problem
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 <= 104
Approach overview
Problem 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 1: Balanced operations towards median
The array arr follows the pattern (2 * i) + 1, making it an arithmetic sequence of odd numbers. The median of the arithmetic sequence is the middle element for odd n and the average of two middle elements for even n. Since operations have to balance the values to become equal, the number of operations required is essentially the sum of steps needed to make the greater half equal to this median, iterating from the middle outwards.
def min_operations(n):
half = n // 2
return half * (half + (n % 2 == 0))
# Example usage
print(min_operations(3)) # Output: 2
print(min_operations(6)) # Output: 9public class Solution {
public int minOperations(int n) {
int half = n / 2;
return half * (half + (n % 2 == 0 ? 1 : 0));
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.minOperations(3)); // Output: 2
System.out.println(sol.minOperations(6)); // Output: 9
}
}#include <iostream>
using namespace std;
int minOperations(int n) {
int half = n / 2;
return half * (half + (n % 2 == 0));
}
int main() {
cout << minOperations(3) << endl; // Output: 2
cout << minOperations(6) << endl; // Output: 9
return 0;
}function minOperations(n) {
let half = Math.floor(n / 2);
return half * (half + (n % 2 === 0 ? 1 : 0));
}
console.log(minOperations(3)); // Output: 2
console.log(minOperations(6)); // Output: 9#include <stdio.h>
int minOperations(int n) {
int half = n / 2;
return half * (half + (n % 2 == 0 ? 1 : 0));
}
int main() {
printf("%d\n", minOperations(3)); // Output: 2
printf("%d\n", minOperations(6)); // Output: 9
return 0;
}using System;
public class Solution {
public int MinOperations(int n) {
int half = n / 2;
return half * (half + (n % 2 == 0 ? 1 : 0));
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.MinOperations(3)); // Output: 2
Console.WriteLine(sol.MinOperations(6)); // Output: 9
}
}The function calculates how many operations are needed by focusing on one half of the array to compute the total steps the elements in this half must take to equalize. The variable half represents the number of operations contributed by each of these elements.
Time Complexity: O(1), since the solution simply computes a formula.
Space Complexity: O(1), as no additional space is required.
Approach 2: Brute Force Simulation (Inefficient but Useful for Understanding)
This approach demonstrates a naive simulation of operations: iteratively balance the array elements by focusing on reducing extreme disparities between elements. This is not intended for efficiency but understanding the process.
def min_operations_naive(n):
arr = [(2 * i) + 1 for i in range(n)]
cnt = 0
target = sum(arr) // n # since n is guaranteed to be odd, this would work
while any(x != target for x in arr):
for i in range(n):
if arr[i] > target:
for j in range(n):
if arr[j] < target:
arr[i] -= 1
arr[j] += 1
cnt += 1
break
return cnt
# Example usage
print(min_operations_naive(3)) # Output: 2
print(min_operations_naive(6)) # Output: 9import java.util.Arrays;
public class Solution {
public int minOperationsNaive(int n) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = (2 * i) + 1;
}
int target = Arrays.stream(arr).sum() / n;
int cnt = 0;
boolean balanced;
do {
balanced = true;
for (int i = 0; i < n; i++) {
if (arr[i] > target) {
for (int j = 0; j < n; j++) {
if (arr[j] < target) {
arr[i]--;
arr[j]++;
cnt++;
balanced = false;
break;
}
}
}
}
} while (!balanced);
return cnt;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.minOperationsNaive(3)); // Output: 2
System.out.println(sol.minOperationsNaive(6)); // Output: 9
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minOperationsNaive(int n) {
vector<int> arr(n);
for (int i = 0; i < n; ++i) {
arr[i] = (2 * i) + 1;
}
int target = accumulate(arr.begin(), arr.end(), 0) / n;
int cnt = 0;
bool balanced = false;
while (!balanced) {
balanced = true;
for (int i = 0; i < n; ++i) {
if (arr[i] > target) {
for (int j = 0; j < n; ++j) {
if (arr[j] < target) {
arr[i]--;
arr[j]++;
cnt++;
balanced = false;
break;
}
}
}
}
}
return cnt;
}
int main() {
cout << minOperationsNaive(3) << endl; // Output: 2
cout << minOperationsNaive(6) << endl; // Output: 9
return 0;
}function minOperationsNaive(n) {
let arr = Array.from({ length: n }, (_, i) => (2 * i) + 1);
let cnt = 0;
const target = arr.reduce((acc, val) => acc + val, 0) / n;
let balanced = false;
while (!balanced) {
balanced = true;
for (let i = 0; i < n; i++) {
if (arr[i] > target) {
for (let j = 0; j < n; j++) {
if (arr[j] < target) {
arr[i]--;
arr[j]++;
cnt++;
balanced = false;
break;
}
}
}
}
}
return cnt;
}
console.log(minOperationsNaive(3)); // Output: 2
console.log(minOperationsNaive(6)); // Output: 9#include <stdio.h>
int minOperationsNaive(int n) {
int arr[n];
for (int i = 0; i < n; ++i) {
arr[i] = (2 * i) + 1;
}
int target = 0;
for (int i = 0; i < n; ++i) {
target += arr[i];
}
target /= n;
int cnt = 0;
int balanced = 0;
while (!balanced) {
balanced = 1;
for (int i = 0; i < n; ++i) {
if (arr[i] > target) {
for (int j = 0; j < n; ++j) {
if (arr[j] < target) {
arr[i]--;
arr[j]++;
cnt++;
balanced = 0;
break;
}
}
}
}
}
return cnt;
}
int main() {
printf("%d\n", minOperationsNaive(3)); // Output: 2
printf("%d\n", minOperationsNaive(6)); // Output: 9
return 0;
}using System;
using System.Linq;
public class Solution {
public int MinOperationsNaive(int n) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = (2 * i) + 1;
}
int target = arr.Sum() / n;
int cnt = 0;
bool balanced;
do {
balanced = true;
for (int i = 0; i < n; i++) {
if (arr[i] > target) {
for (int j = 0; j < n; j++) {
if (arr[j] < target) {
arr[i]--;
arr[j]++;
cnt++;
balanced = false;
break;
}
}
}
}
} while (!balanced);
return cnt;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.MinOperationsNaive(3)); // Output: 2
Console.WriteLine(sol.MinOperationsNaive(6)); // Output: 9
}
}This technique creates the array and iteratively applies moves to gradually level the array. It evaluates each pairing of elements in a nested loop fashion, conducting operations until all elements stabilize at the target value.
Time Complexity: O(n^2), due to nested iterations looking for disparities.
Space Complexity: O(n), to store the array.
Approach 3: Mathematics
According to the problem description, the array arr is an arithmetic sequence with the first term as 1 and the common difference as 2. Therefore, the sum of the first n terms of the array is:
$
\begin{aligned}
S_n &= \frac{n}{2} times (a_1 + a_n) \
&= \frac{n}{2} times (1 + (2n - 1)) \
&= n^2
\end{aligned}
Since in one operation, one number is decreased by one and another number is increased by one, the sum of all elements in the array remains unchanged. Therefore, when all elements in the array are equal, the value of each element is S_n / n = n. Hence, the minimum number of operations required to make all elements in the array equal is:
sum_{i=0}^{\frac{n}{2}} (n - (2i + 1))
The time complexity is O(n), where n is the length of the array. The space complexity is O(1)$.
function minOperations(n: number): number {
let ans = 0;
for (let i = 0; i < n >> 1; ++i) {
ans += n - ((i << 1) | 1);
}
return ans;
}func minOperations(n int) (ans int) {
for i := 0; i < n>>1; i++ {
ans += n - (i<<1 | 1)
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Balanced operations towards median | Time Complexity: O(1), since the solution simply computes a formula. |
| Brute Force Simulation (Inefficient but Useful for Understanding) | Time Complexity: O(n^2), due to nested iterations looking for disparities. |
| Mathematics | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Minimum Operations to Make Array Equal easy or hard?
The problem is rated Medium because the optimal solution requires recognizing a mathematical pattern rather than performing direct simulation. Once the symmetry of the array is understood, the solution reduces to a simple formula.
Minimum Operations to Make Array Equal Python/Java solution
In Python or Java, the optimal solution computes floor(n*n/4). For even n the result is (n/2)*(n/2), and for odd n it is (n//2)*(n//2 + 1). This constant-time calculation avoids building the array or simulating operations.
How to solve Minimum Operations to Make Array Equal in O(n)?
Iterate through the first half of the array where arr[i] = 2*i + 1. For each element, calculate how far it is from the target value n and accumulate the difference n - (2*i + 1). Each unit difference corresponds to one operation transferred from the right side. Summing these values produces the total operations in O(n) time and O(1) space.
What is the best approach for Minimum Operations to Make Array Equal?
The best approach uses a mathematical observation about the symmetric array [1,3,5,...]. Every value must become the mean, which equals n. By summing the deficits of the left half of the array, the total operations simplify to floor(n^2 / 4). This gives an O(1) time and O(1) space solution.
Is Minimum Operations to Make Array Equal asked at Google/Amazon/Meta?
Problems based on mathematical observations and array balancing appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact question may vary, the core idea of identifying symmetry and deriving a formula is a common interview pattern.
What data structure is used in Minimum Operations to Make Array Equal?
The problem primarily relies on mathematical reasoning rather than advanced data structures. The array structure arr[i] = 2*i + 1 is analyzed directly, and the optimal solution uses arithmetic properties and symmetry instead of additional storage.
What is the time complexity of Minimum Operations to Make Array Equal?
The optimal mathematical solution runs in O(1) time because the result can be computed directly using the formula floor(n^2 / 4). A more explanatory approach that sums differences across half the array runs in O(n). A brute force simulation can degrade to O(n^2).