Minimum Operations to Make Array Equal

Problem Description

You have an array arr of length n where arr[i] = (2 * i) + 1 for all valid values of i. In one operation, you can select two indices x and y and perform arr[x] -= 1 and arr[y] += 1. The goal is to make all the elements of the array equal. Given an integer n, return the minimum number of operations needed to make all the elements of arr equal.

Key Insights

• The array arr consists of the first n odd numbers.
• The average value of the array can be calculated as n^2.
• The total difference from the average can be computed based on how far each element is from this average.
• The number of operations needed is essentially half of the total difference from the average since each operation can adjust two elements.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

To solve the problem, we note that the array arr is a sequence of odd numbers. The average of the array will be the middle value, which can be calculated as n^2. To equalize all elements, we compute how much each element must move towards this average. The total number of operations required to achieve this is half the sum of the differences from the average, as one operation affects two elements.

Code Solutions