Problem statement
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.
Problem statement taken from: https://leetcode.com/problems/minimum-operations-to-make-array-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 <= 10^4
Explanation
Brute Force
As per the problem statement, the value at index i in the array is equal to (2 * i) + 1. The array of size n can be represented as follows:
arr = [2 * 0 + 1, 2 * 1 + 1, 2 * 2 + 1,.... 2 * (n - 1) + 1]
when n = 6
arr = [2 * 0 + 1, 2 * 1 + 1, 2 * 2 + 1, 2 * 3 + 1, 2 * 4 + 1, 2 * 5 + 1]
= [1, 3, 5, 7, 9, 11]
when n = 7
arr = [1, 3, 5, 7, 9, 11, 13]
The array elements are ordered in a linear arithmetic series. Let's calculate the number of operations at each step.
arr = [1, 3, 5, 7, 9, 11, 13]
First operation, we will increase arr[0] = 1 by 1 and decrease arr[6] = 13 by 1.
arr = [2, 3, 5, 7, 9, 11, 12]
We repeat the above process till arr[0] and arr[6] = 7
Number of operations = 6
Similarly, for arr[1] and arr[5], the number of operations to update value to 7 will be 4.
For arr[2] and arr[4], the number of operations will be 2.
Total number of operations = 6 + 4 + 2
= 12
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17]
First operation, we will increase arr[0] = 1 by 1 and decrease arr[8] = 17 by 1.
arr = [2, 3, 5, 7, 9, 11, 13, 15, 16]
We repeat the above process till arr[0] and arr[8] = 9
Number of operations = 8
Similarly, for arr[1] and arr[7], the number of operations to update the value to 9 will be 6.
For arr[2] and arr[6], the number of operations will be 4.
For arr[3] and arr[5], the number of operations will be 2.
Total number of operations = 8 + 6 + 4 + 2
= 20
From the above pattern, we observe at any step or index i, the number of operations is n - 2 * i - 1. The total number of operations will be
number_of_operations = 0
for(int i = 0; i < n / 2; i++) {
number_of_operations += n - (2 * i) - 1
}
return number_of_operations
The time complexity of the above approach is O(n), and the space complexity is O(1).
Efficient approach
We can further optimize the above approach. Let's observe the pattern for the number of operations. For every i = 0, 1, 2,...(n/2) - 1, we get the series as
n - 1, n - 3, n - 5,.......7, 5, 3, 1.
This is an arithmetic series a, a + d, a + 2d...., where a = 1 and d = 2. The arithmetic sum of this series is
sum = n * (2 * a + (n - 1) * d) / 2
In our case, n = n / 2. We apply the above formula
sum = (n / 2) * (2 * 1 + (n/2 - 1) * 2) / 2
= n * (2 + (n - 2)) / 4
= n * (n) / 4
= (n * n) / 4
When n is odd, the arithmetic series is n - 1, n - 3,....5, 3, 1. When n is even, the arithmetic series is n - 1,...6, 4, 2. We apply the same arithmetic series formula, reducing the sum to (n * n) / 4.
The time and space complexity of the above approach is O(1).
Let's check our algorithm in C++, Golang, and JavaScript.
C++ solution
class Solution {
public:
int minOperations(int n) {
return (n * n) >> 2;
}
};
Golang solution
func minOperations(n int) int {
return (n * n) >> 2
}
JavaScript solution
var minOperations = function(n) {
return (n * n) >> 2;
};
For n = 6, we return the solution as (6 * 6) >> 2 = 9.
Top comments (0)