How to Answer: Use minimum operations to make an array equal.
Advice and answer examples written specifically for a JavaScript Intermediate Level Implementation job interview.
3. Use minimum operations to make an array equal.
This question shows the developer's ability to use JavaScript passes and properties.
You are given a positive integer n. You generate an array of length n such that arr[i] = 2 * i + 1 where 0 <= i < n. You perform a series of operations on the array to make all the elements of the array equal. In one operation, you choose two indices of the array i and j and subtract 1 from arr[i], and add 1 to arr[j]. Your task is to calculate the minimum number of operations required to make all the elements of the array equal.
/*Example*/
Given n = 3
Expected output:- 2
Explanation: the generated array is [1, 3, 5]
In the first operation we choose i = 0 and j = 2, so the array becomes [2, 3, 4]
In the second operation we choose i = 0 and j = 2, so the array becomes [3, 3, 3]Solution:
Approach I (one pass):
In this approach, we will iterate over the half elements of the generated array and find the number of operations to make them equal to mid. All the elements in the array will be equal to mid after those operations. There are two cases that we need to see: when n is odd and when n is even.
When n is odd: When n is odd, it can be observed that, the minimal way to make all the elements equal is to make them equal to the middle element of the array. The middle element is at index midIndex = (n - 1) / 2. The value at i = midIndex is:
mid = arr[midIndex] = 2 * midIndex + 1 = n
Thus, we will make all the elements equal to n. For example,
when n = 5,
=> arr = [1, 3, 5, 7, 9]
=> midIndex = 2
=> mid = 5 = n
In one operation we will choose opposite indices. For example, we will choose (0, 4) or (1, 3). This will make the process easier. Since we increase and decrease simultaneously, we need to iterate over only either the lower indices or the higher indices from midIndex (let’s iterate over lower indices). The number of elements below lower indices are countTerms = (n - 1) / 2.
When n is even: When n is even, it can be observed that, the minimal way to make all the elements equal is to make them equal to the mean of the middle two elements. For example,
when n = 6
=> arr = [1, 3, 5, 7, 9, 11]
The optimal way is to make all of them equal to 6 (mean of 5 and 7). In this case, too, the value of mid is n, that is mid = n.
The same argument applies that we will iterate over lower indices only (or higher indices only). The number of elements below lower indices are countTerms = n / 2.
/**
* @param {number} n
* @return {number}
*/
function minOperations(n) {
const mid = n
let ans = 0
let countTerms
if (n % 2 === 0) {
countTerms = (n - 1) / 2
} else {
countTerms = n / 2
}
for (let i = 0; i < countTerms; i++) {
const term = 2 * i + 1
ans += mid - term
}
return ans
}Time complexity- O(n)
Space complexity- O(n)
Approach II (using AP properties):
As in the previous approach, the value of the mid element remains the same. There is an important observation while applying operation on a pair of indices.
When n is odd: Let us assume the array is [1, 3, 5, …, n, n + 2, …, 2 * n - 1]. The mid element is n which is also odd. The increments required for the lower indices are: n - 1, n - 3, …., 6, 4, 2 which is an AP with first term n - 1 and difference equal to 2. The sum of this AP will be the number of operations required to make all the elements of the array equal. The sum of the AP is:
sum = (first_term + last_term) * no_of_terms / 2
= (n - 1 + 2) * countTerms / 2
= (n + 1) * (n - 1) / 4
When n is even: Let us assume the array is [1, 3, 5, …, n, n + 2, …, 2 * n - 1]. The mid element is n which is also even. The increments required for the lower indices are: n - 1, n - 3, …., 5, 3, 1 which is an AP with first term n - 1 and difference equal to 2. The sum of this AP will be the number of operations required to make all the elements of the array equal. The sum of the AP is:
sum = (first_term + last_term) * no_of_terms / 2
= (n - 1 + 1) * countTerms / 2
= n * n / 4
/**
* @param {number} n
* @return {number}
*/
function minOperations(n) {
if (n % 2 === 1) {
return (n + 1) * (n - 1) / 4
}
return n * n / 4
}Time complexity- O(1)
Space complexity- O(1)
Written by S. Kumar on June 27th, 2021