Vultr DocsLatest Content

Minimum Operations to Make Array Equal

Updated on 12 June, 2025
Minimum Operations to Make Array Equal header image

Problem Statement

You are provided with an array arr that has a specific formula with respect to its indices: for each index i (where 0 <= i < n), arr[i] = (2 * i) + 1. This means that the array contains consecutively increasing odd integers starting from 1. The task involves operations where you can select any two indices x and y (with 0 <= x, y < n) and reallocate units by subtracting 1 from arr[x] and adding 1 to arr[y]. The ultimate objective is to adjust the array so all its elements become equal. To accomplish this, you need to determine the minimum number of operations required. Importantly, it is assured that such a transformation is achievable for any given n.

Examples

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

Approach and Intuition

The problem essentially reduces to redistributing the values amongst the array elements to achieve uniformity across the board. Here’s a step-by-step breakdown of how one might think about the solution:

  1. Calculate the final uniform value each array element needs to reach. This can be deduced by calculating the mean of initial array values since the total sum remains constant while redistributing.

    • For an array derived from the formula (2 * i) + 1, the total sum of the array when n elements are considered is given by the formula for the sum of the first n odd numbers: n^2.
    • The final uniform value for each element thus becomes n^2 / n = n.

  2. Determine the amount of increment or decrement required by each element to reach the mean value:

    • Each index i in arr initially holds a value of (2*i) + 1. The difference from the mean for each element is ((2*i) + 1) - n.
    • If this difference is positive, arr[i] has excess and needs to distribute this excess to other elements. If it’s negative, arr[i] requires that many units to reach equilibrium.

  3. Calculate the total number of operations required:

    • Since each operation involves transferring a single unit, the minimum number of operations needed is essentially the sum of all positive differences (or equivalently, the sum of the absolute values of the negative differences due to the constant sum).
    • Alternately, calculating half the total absolute difference gives you the operations count since each positive excess matches a negative need.

This calculation gives an intuitive grasp on balancing an array wherein the number of operations is directly tied to redistributing the excesses calculated against the average.

Solutions

  • Java
  • Python
java 
class Solution {
    public int minimumOperations(int number) {
        if (number % 2 == 0) {
            return (number * number) / 4;
        } else {
            return ((number * number) - 1) / 4;
        }
    }
}

The problem titled "Minimum Operations to Make Array Equal" involves calculating the minimum number of moves required to make all elements in an array of integers equal using specific operations. The provided solution is written in Java.

Here's the breakdown:

  • The function minimumOperations accepts an integer number which represents the number of elements in the hypothetical array.
  • If number is even, the function calculates the result by squaring number and then dividing by four.
  • If number is odd, it first computes (number * number) - 1 and then divides the result by four.

This approach leverages a mathematical pattern observed for modifying arrays into a state of equality through specific operations. Based on the input size, the solution determines the minimum operations needed using straightforward arithmetic and branching operations. It offers a direct calculation resulting in efficient execution with a time complexity of O(1) due to the absence of loops or recursive calls.

python 
class Solution:
    def minimumOperations(self, number: int) -> int:
        return number**2 // 4 if number % 2 == 0 else (number**2 - 1) // 4

This Python solution efficiently calculates the minimum number of operations required to make all elements of an array equal, given its size. The function minimumOperations uses the mathematical properties of even and odd integers:

  • For an even-sized array defined by number, the necessary operations are (number**2) // 4.
  • For an odd-sized array, the required operations adjust as ((number**2) - 1) // 4.

This approach leverages integer division and squaring to achieve the result succinctly. The exploitation of even and odd characteristics simplifies the computation, obviating the need for iterative or complex algorithms.

Comments

No comments yet.