Minimum Operations to Make Array Equal — Problem & Solution
Minimum Operations to Make Array Equal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Operations to Make Array Equal is a medium coding problem on math, asked in Amazon and Adobe interviews.
- Difficulty: Medium
- Topics: Math
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have an array arr of length n where arr[i] = 2 * i + 1 for every i, so arr is [1, 3, 5, …, 2n-1].
In one operation you pick two indices x and y, subtract 1 from arr[x] and add 1 to arr[y]. Return the minimum number of operations needed to make all elements equal. It is always possible.
Example 1
Input: n = 3
Output: 2
Explanation: [1,3,5] → [2,3,4] → [3,3,3].
Example 2
Input: n = 6
Output: 9
Example 3
Input: n = 1
Output: 0
Explanation: A single element is already equal to itself.
Constraints
1 <= n <= 10000
Hints for Minimum Operations to Make Array Equal
Hint 1
The array is an arithmetic sequence, so its mean is
n— that is the value everything must reach.Hint 2
Each operation moves one unit from an element above the mean to one below it.
Hint 3
The answer is the total surplus: the sum of
arr[i] - nover the elements above the mean.
How to solve Minimum Operations to Make Array Equal
Every operation transfers exactly one unit from a high element to a low one, so the minimum count is the total amount that must be moved — the surplus above the mean.
Approach
- Note the mean is
n, sincearris1, 3, …, 2n-1and its average isn. - Sum the surplus
arr[i] - nover the top half of the array. - That sum works out to
floor(n² / 4), so return it directly.
Why it works
The array is symmetric about n: the surplus above equals the deficit below. Summing (2i+1) - n for the elements above the mean gives 2 + 4 + … , telescoping to n²/4 for even n and (n²-1)/4 for odd n — both floor(n²/4). No operation can move more than one unit, so this is also a lower bound.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
- Summing the whole array's deviation double-counts — the moved units are counted once at each end.
n * nreaches 10^8 here, safely inside 32 bits, but the habit of widening first is cheap.
Reference solution
Python
def minOperations(n: int) -> int:
return n * n // 4Java
public static int minOperations(int n) {
return (int) ((long) n * n / 4);
}C++
int minOperations(int n) {
return (int) ((long long) n * n / 4);
}JavaScript
var minOperations = function(n) {
return Math.floor((n * n) / 4);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.