Advertisement
Home Data Structure Arrays Minimum Number of Operations to Make Array Equal

Minimum Number of Operations to Make Array Equal

0
Advertisement

Title: Minimum Number of Operations to Make Array Equal

In this guide, you’ll learn how to solve the Minimum Number of Operations to Make Array Equal problem, a classic LeetCode array challenge that tests how comfortable you are reasoning about medians, pairwise differences, and two-pointer techniques.

You are given a single integer n. From it, an array arr of length n is implicitly defined as arr[i] = 2 * i + 1 for every valid index i, so arr always looks like [1, 3, 5, ..., 2n - 1]. In one operation you may pick any two indices x and y and perform arr[x]-- and arr[y]++. Your task is to return the minimum number of such operations needed to make every element of arr equal.

Understanding the Problem

Every operation moves exactly one unit from one element to another, so the total sum of the array never changes. That means the only value every element can converge to is the array’s mean, which for this sequence always works out to n itself.

Because the array is symmetric around n (the smallest and largest elements are always the same distance from the center), you do not need to build the array or compute an average explicitly. You can reason about it pair by pair, from the outside in.

Constraints: 1 <= n <= 10,000. It is guaranteed that the elements can always be made equal, so you never need to handle an unsolvable case.

Approach

The cleanest way to solve this without ever materializing arr is a two-pointer walk from both ends toward the middle:

  1. Recognize that arr[i] = 2 * i + 1, so the array never needs to be built; only the indices matter.
  2. Initialize two pointers, left = 0 and right = n - 1, plus a counter operations = 0.
  3. While left is strictly less than right, add right - left to operations; this is the number of unit moves needed to bring the pair arr[left] and arr[right] level with every pair already equalized.
  4. Move the pointers one step toward the center: left++ and right--.
  5. Stop once left meets or passes right; every element has either already been the target value or been paired off with its mirror on the other side.
  6. Return operations as the minimum number of moves.

Java Program

Java
public class MinimumOperationsArrayEqual {

    public static int minOperations(int n) {
        int left = 0;
        int right = n - 1;
        int operations = 0;

        while (left < right) {
            operations += (right - left);
            left++;
            right--;
        }

        return operations;
    }

    public static void main(String[] args) {
        int n1 = 3;
        System.out.println("n = " + n1 + " -> operations = " + minOperations(n1));

        int n2 = 1;
        System.out.println("n = " + n2 + " -> operations = " + minOperations(n2));

        int n3 = 8;
        System.out.println("n = " + n3 + " -> operations = " + minOperations(n3));
    }
}

Explanation of the Program

The minOperations method never allocates an array. It only tracks three integers: left, right, and operations.

  • left and right start at the two ends of the implicit array and walk toward each other.
  • On each iteration, right - left is exactly how far arr[right] and arr[left] each sit from the center value n; adding it to operations accounts for moving both of them to the middle in one combined step.
  • The loop stops the moment left and right meet or cross, meaning every element either already sits at the center (for odd n) or has been paired off with its mirror.
  • main simply calls minOperations with a few sample values of n and prints the results so you can see the method in action.

Step-by-Step Trace

Trace minOperations(5), where the implicit array is [1, 3, 5, 7, 9] and the expected output is 6:

Iterationleftrightright – leftoperations (before)operations (after)
104404
213246

After each iteration, operations holds the exact number of moves needed to equalize every element outside the current [left, right] window, and the window itself still represents the same type of symmetric subproblem, just one step smaller.

Examples

Example 1: Odd-Length Array

For n = 3 the implicit array is [1, 3, 5]; moving 2 units from index 2 to index 0 equalizes everything at the center value 3.

Java
int n = 3;
// arr = [1, 3, 5], target value = 3
System.out.println(minOperations(n));
// Output: 2

Example 2: Single Element

For n = 1 the array is just [1], which is already uniform, so no operations are required.

Java
int n = 1;
// arr = [1], already equal
System.out.println(minOperations(n));
// Output: 0

Example 3: Larger Even Array

For n = 8 the implicit array is [1, 3, 5, 7, 9, 11, 13, 15]; four symmetric pairs need to collapse toward the middle.

Java
int n = 8;
// arr = [1, 3, 5, 7, 9, 11, 13, 15]
System.out.println(minOperations(n));
// Output: 16

Common Mistakes to Avoid

These are the slip-ups that most often turn this problem from a one-line formula into a wrong answer.

  • Forgetting to halve the total deviation – summing |arr[i] - n| directly and returning it un-halved doubles the real answer, since every operation changes the total deviation by two (one -1 and one +1). Divide the summed deviation by 2, or use the right - left two-pointer term which already accounts for both sides at once.
  • Using left <= right instead of left < right – for odd n this compares the middle index against itself, which signals you don’t realize the middle element never has to move. Keep the loop condition strictly left < right.
  • Materializing the actual array – writing int[] arr = new int[n] and filling it with 2 * i + 1 works but wastes O(n) memory and time that plain index arithmetic avoids entirely. Compute right - left straight from the indices and never allocate the array.
  • Letting n * n overflow in the closed form – for very large values of n, n * n can exceed Integer.MAX_VALUE and silently wrap to a negative number. Widen to long before multiplying, e.g. (long) n * n / 4.

Edge Cases to Test

Walk through these inputs out loud before you call the method done.

  • n = 1 (single-element array, zero operations)
  • n = 2 (smallest two-element pair, exactly one operation)
  • Even values of n (array splits into perfect pairs with no middle element)
  • Odd values of n (middle element already sits at the target)
  • Maximum allowed n = 10,000 (checks performance and that the running total stays well within int range)
  • Back-to-back calls with different n values on the same method (confirms it holds no state between calls)

Additional Considerations

The two-pointer solution runs in O(n) time and O(1) extra space, since it only ever touches left, right, and operations.

Because arr[i] = 2 * i + 1 is a fixed arithmetic sequence, the loop’s final total is actually a closed form: it always equals n * n / 4 using integer division. You could replace the whole loop with return n * n / 4; for an O(1) solution; the two-pointer version is kept here because it mirrors how you would reason about the general ‘equalize to the median’ pattern when the input is an arbitrary array rather than this fixed sequence.

Both versions agree on every input, so pick the loop when you want to explain your reasoning out loud in an interview, and the closed form when you want the fastest possible code.

Interview Follow-up Questions

Once you’ve nailed the base case, expect an interviewer to push on these variations.

  • What if you were given the actual array instead of just n? – sort it first, then the same two-pointer walk toward the median works for any array, not just this fixed sequence.
  • What if the cost of an operation grew with distance instead of staying fixed at 1? – minimizing total absolute distance still points to the median, but minimizing total squared distance would point to the mean instead.
  • What if you need the actual list of moves, not just the count? – emit the pair (left, right) on every iteration of the two-pointer loop instead of only accumulating the count.
  • What if n were enormous, say in the billions, and you cannot loop at all? – fall back to the closed form (long) n * n / 4, which answers in O(1) time with no iteration.
  • What if you had to solve it with strictly O(1) extra memory and no helper pointers whatsoever? – return the closed-form expression directly; it needs no mutable state at all.

Conclusion

The Minimum Number of Operations to Make Array Equal problem is really a lesson about medians and symmetry wearing an array-manipulation costume. Once you see that the array is a fixed arithmetic sequence centered on n, the two-pointer walk, or the one-line formula, falls out naturally.

Try adapting the same median-and-pairwise-distance idea to problems that hand you an arbitrary unsorted array instead of this fixed sequence; sorting first and then applying the same two-pointer walk generalizes surprisingly well. You can find more problems like this one in the Arrays section of the blog.