010.md

1551. Minimum Operations to Make Array Equal

Difficulty: 🟡 Medium

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.

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

Solutions

Read explanation here.

O(1) solution

Python3

class Solution(object):
    def minOperations(self, n):
        """
        :type n: int
        :rtype: int
        """
        return n * n // 4

The given solution solves the problem using a mathematical approach. It calculates the minimum number of operations required by dividing the sum of the array arr by n (which represents the target value each element should have). The formula used to calculate the sum of the array is (n * n) // 4, where // represents integer division.

The algorithm performs the following steps:

1. Calculate the target value that each element of arr should have, which is the sum of arr divided by n. The formula used is (n * n) // 4.
2. Return the target value as the minimum number of operations required to make all elements of arr equal.

Complexity Analysis

The time complexity of this algorithm is O(1) because it performs a constant number of mathematical operations.

The space complexity of the algorithm is O(1) because it uses a fixed amount of additional space to store the intermediate result.

Summary

The given solution determines the minimum number of operations required to make all elements of the array arr equal. It uses a mathematical approach by calculating the target value each element should have. The algorithm has a time complexity of O(1) and a space complexity of O(1), making it efficient for the given constraints.

NB: If you want to get community points please suggest solutions in other languages as merge requests.