Scale Engineer

Minimum Operations to Make Array Equal

Med
#1428Time: O(n) - We iterate through the array twice: once to populate it (O(n)) and once to calculate the operations for the first half (O(n/2)). This simplifies to O(n).Space: O(n) - We explicitly create an integer array of size `n` to store the values.
Patterns
Math

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach simulates the problem by first constructing the array as described, then calculating the target value, and finally iterating through the array to sum up the necessary operations.

Algorithm

  • Create an integer array arr of size n.
  • Populate the array such that arr[i] = (2 * i) + 1 for i from 0 to n-1.
  • Initialize a variable operations to 0.
  • The target value for all elements to be equal is n.
  • Iterate from i = 0 to n / 2 - 1. The elements in this range are all smaller than the target n.
  • For each arr[i], calculate the difference n - arr[i] and add it to operations.
  • Return operations.

Walkthrough

The core idea is to determine the final equal value all elements must have. Since each operation subtracts 1 from one element and adds 1 to another, the total sum of the array elements remains constant. Therefore, the final value for each element must be the average of the initial elements.

The array is an arithmetic progression 1, 3, 5, .... The sum of its n elements is n^2. Thus, the target value for each element is n^2 / n = n.

The number of operations is the total amount that needs to be added to elements smaller than the target n. We only need to consider the first half of the array, as these are the elements smaller than n. The elements in the second half are symmetrically larger than n.

class Solution {    public int minOperations(int n) {        if (n <= 1) {            return 0;        }        int[] arr = new int[n];        for (int i = 0; i < n; i++) {            arr[i] = (2 * i) + 1;        }                int target = n;        int operations = 0;        for (int i = 0; i < n / 2; i++) {            operations += target - arr[i];        }                return operations;    }}

Complexity

Time

O(n) - We iterate through the array twice: once to populate it (O(n)) and once to calculate the operations for the first half (O(n/2)). This simplifies to O(n).

Space

O(n) - We explicitly create an integer array of size `n` to store the values.

Trade-offs

Pros

  • Simple to understand and directly follows the problem description.

Cons

  • Inefficient in terms of space, as creating the array is not strictly necessary and consumes memory proportional to n.

Solutions

class Solution {public  int minOperations(int n) {    int ans = 0;    for (int i = 0; i < n >> 1; ++i) {      ans += n - (i << 1 | 1);    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem