Leetcode 1551. Minimum Operations to Make Array Equal

Problem

The problem asks to perform some operations on an array. In each operation, we can select any two indices, subtract 1 from one index, and add 1 to another index with the goal to make all elements equal. The initial array contains elements with values (2*i)+1 where i is between 0 and n-1.

We are required to calculate the minimum number of operations required to make all the elements of the array equal.

Examples

Let's consider the example, n = 3.

The initial array will be [1,3,5].

We could subtract one from index 2 (element value = 5) and add it to index 0 (element value = 1). Then our array becomes [2, 3, 4].

Performing the same operation again will finally make all elements equal, so our array becomes [3,3,3]. Therefore, it took us 2 operations to make all elements the same.

Approach

The solution counts the difference between each pair of elements from the start and the end of the array until they meet in the middle, which represents the number of operations needed to make both elements equal.

Since we know the array is sorted and evenly distributed, the difference for each pair will increase by 2 for each step. Therefore, we can compute the sum using the formula for the sum of an arithmetic series: (first_term + last_term) * number_of_terms / 2 where number_of_terms = n/2, first_term = 1, and last_term = n - 2 (for even n) or n - 1 (for odd n).

Solution

Python Solution

1
2python
3class Solution:
4    def minOperations(self, n: int) -> int:
5        return n*n // 4

JAVA Solution

1
2Java
3class Solution {
4    public int minOperations(int n) {
5        return n * n / 4;
6    }
7}

JavaScript Solution

1
2javascript
3var minOperations = function(n) {
4    return Math.floor(n * n / 4);
5};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int minOperations(int n) {
6        return n * n / 4;
7    }
8};

C# Solution

1
2csharp
3public class Solution {
4    public int MinOperations(int n) {
5        return n * n / 4;
6    }
7}

All the above solutions will give the minimum number of operations needed to make all the elements in the array equal. The time complexity for the solutions is O(1), as the solutions only involve arithmetic calculations, not depending on the size of n.# Explanation

The problem involves working with an array that is sorted and evenly distributed. We want to make all elements equal using the least number of operations of adding or subtracting 1 between two indices in the array.

The formulas (first_term + last_term) * number_of_terms / 2 for the sum of an arithmetic series and the term (2*i)+1 for array elements are key to understanding the problem. These formulas show that the approach is based on finding the average of our series to which we will aim to converge all the values. Given that each operation brings two values closer to the average by +/- 1, the minimum number of operations can be calculated as the sum of differences of each pair from the average.

In the series, the first term is 1 and the last term is n - 2 (for even n) or n - 1 (for odd n). But we only need to use half of the values (n//2), because each operation affects two terms. Furthermore, due to the arithmetic nature of the series, the sum of differences between pairs from the average can be simplified to n * n / 4.

In effect, this solution leverages the properties of arithmetic series and the equal increments of the first term and decrements of the last term. Does that make sense? It embraces the beauty of arithmetic progression and is a real brain teaser!

Review

In a nutshell, this problem is a great opportunity to brush up your skills to work with arithmetic series. The provided solution is quite the most optimal one, with a constant time complexity O(1) and constant space complexity O(1), as it only uses a simple arithmetic calculation that not depends on the size of the array n. So, in terms of time and space efficiency, the solutions are doing excellent and don't leave much room for improvement. However, understanding the underlying concept of the arithmetic series and its application forms the crux of cracking this problem.

In terms of code readability and maintainability, the code looks clean, well-structured and compact. Even without comments, it is easy to understand what the function is doing by reading the code. This simplicity is made possible because of the mathematical elegance of the problem at hand. Remember, the beauty of mathematics lies not only in its complexity, but also in its simplicity!


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫