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.
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 <= 104The array arr follows the pattern (2 * i) + 1, making it an arithmetic sequence of odd numbers. The median of the arithmetic sequence is the middle element for odd n and the average of two middle elements for even n. Since operations have to balance the values to become equal, the number of operations required is essentially the sum of steps needed to make the greater half equal to this median, iterating from the middle outwards.
The function calculates how many operations are needed by focusing on one half of the array to compute the total steps the elements in this half must take to equalize. The variable half represents the number of operations contributed by each of these elements.
C++
Java
C#
JavaScript
C
Time Complexity: O(1), since the solution simply computes a formula.
Space Complexity: O(1), as no additional space is required.
This approach demonstrates a naive simulation of operations: iteratively balance the array elements by focusing on reducing extreme disparities between elements. This is not intended for efficiency but understanding the process.
This technique creates the array and iteratively applies moves to gradually level the array. It evaluates each pairing of elements in a nested loop fashion, conducting operations until all elements stabilize at the target value.
C++
Java
C#
JavaScript
C
Time Complexity: O(n^2), due to nested iterations looking for disparities.
Space Complexity: O(n), to store the array.
| Approach | Complexity |
|---|---|
| Balanced operations towards median | Time Complexity: O(1), since the solution simply computes a formula. |
| Brute Force Simulation (Inefficient but Useful for Understanding) | Time Complexity: O(n^2), due to nested iterations looking for disparities. |
Minimum Operations to Make Array Equal | Leetcode - 1551 • Algorithms Made Easy • 24,165 views views
Watch 9 more video solutions →Practice Minimum Operations to Make Array Equal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor