Minimum Operations to Make Array Equal

Medium
552.

Minimum Operations to Make Array Equal

Minimum Operations to Make Array Equal is a medium coding problem on math, asked in Amazon and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var minOperations = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    The array is an arithmetic sequence, so its mean is n — that is the value everything must reach.

  2. Hint 2

    Each operation moves one unit from an element above the mean to one below it.

  3. Hint 3

    The answer is the total surplus: the sum of arr[i] - n over 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

  1. Note the mean is n, since arr is 1, 3, …, 2n-1 and its average is n.
  2. Sum the surplus arr[i] - n over the top half of the array.
  3. 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 * n reaches 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 // 4

Java

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.

All 337 math problems · the whole catalogue