LeetCode - Minimum Operations to Make Array Equal

Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/minimum-operations-to-make-array-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 <= 10^4

Explanation

Brute Force

As per the problem statement, the value at index i in the array is equal to (2 * i) + 1. The array of size n can be represented as follows:

arr = [2 * 0 + 1, 2 * 1 + 1, 2 * 2 + 1,.... 2 * (n - 1) + 1]

when n = 6
arr = [2 * 0 + 1, 2 * 1 + 1, 2 * 2 + 1, 2 * 3 + 1, 2 * 4 + 1, 2 * 5 + 1]
    = [1, 3, 5, 7, 9, 11]

when n = 7
arr = [1, 3, 5, 7, 9, 11, 13]

The array elements are ordered in a linear arithmetic series. Let's calculate the number of operations at each step.

arr = [1, 3, 5, 7, 9, 11, 13]

First operation, we will increase arr[0] = 1 by 1 and decrease arr[6] = 13 by 1.
arr = [2, 3, 5, 7, 9, 11, 12]

We repeat the above process till arr[0] and arr[6] = 7

Number of operations = 6

Similarly, for arr[1] and arr[5], the number of operations to update value to 7 will be 4.
For arr[2] and arr[4], the number of operations will be 2.

Total number of operations = 6 + 4 + 2
                           = 12

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17]

First operation, we will increase arr[0] = 1 by 1 and decrease arr[8] = 17 by 1.
arr = [2, 3, 5, 7, 9, 11, 13, 15, 16]

We repeat the above process till arr[0] and arr[8] = 9

Number of operations = 8

Similarly, for arr[1] and arr[7], the number of operations to update the value to 9 will be 6.
For arr[2] and arr[6], the number of operations will be 4.
For arr[3] and arr[5], the number of operations will be 2.

Total number of operations = 8 + 6 + 4 + 2
                           = 20

From the above pattern, we observe at any step or index i, the number of operations is n - 2 * i - 1. The total number of operations will be

number_of_operations = 0

for(int i = 0; i < n / 2; i++) {
    number_of_operations += n - (2 * i) - 1
}

return number_of_operations

The time complexity of the above approach is O(n), and the space complexity is O(1).

Efficient approach

We can further optimize the above approach. Let's observe the pattern for the number of operations. For every i = 0, 1, 2,...(n/2) - 1, we get the series as

n - 1, n - 3, n - 5,.......7, 5, 3, 1.

This is an arithmetic series a, a + d, a + 2d...., where a = 1 and d = 2. The arithmetic sum of this series is

sum = n * (2 * a + (n - 1) * d) / 2

In our case, n = n / 2. We apply the above formula

sum = (n / 2) * (2 * 1 + (n/2 - 1) * 2) / 2
    = n * (2 + (n - 2)) / 4
    = n * (n) / 4
    = (n * n) / 4

When n is odd, the arithmetic series is n - 1, n - 3,....5, 3, 1. When n is even, the arithmetic series is n - 1,...6, 4, 2. We apply the same arithmetic series formula, reducing the sum to (n * n) / 4.

The time and space complexity of the above approach is O(1).

Let's check our algorithm in C++, Golang, and JavaScript.

C++ solution

class Solution {
public:
    int minOperations(int n) {
        return (n * n) >> 2;
    }
};

Golang solution

func minOperations(n int) int {
    return (n * n) >> 2
}

JavaScript solution

var minOperations = function(n) {
    return (n * n) >> 2;
};

For n = 6, we return the solution as (6 * 6) >> 2 = 9.