Minimum Operations to Make Array Equal: Understanding the Thought Process for Interviews and Leetcoding
This is a standard algorithmic problem confirmed to have been asked in many technical interviews. This problem appeared in the April 2021 Leetcode monthly challenge with the difficulty of Medium. Whether you are prepping for a technical interview or you are just an algorithm lover like me, I strongly believe this post will make an interesting read.
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.
Example
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].
SOLUTION
When faced with this kind of problem in an interview, what would be your first step? Given such an array,
1) How do you find the target number, i.e. the number that all other elements should be equal to?
2) Since operations are performed between pairs of elements in the array, how can we optimally select which pair to operate on?
Identify Patterns: Brute-Force
The first and best step to solving any algorithmic problems that are new to you is always to try to observe some common patterns using few test cases.
Now, we’ll study two test arrays by considering all possible arrangements of pairs of elements in each of the arrays. That way, the first pair in each arrangement will be used to generate the target number and we will try to reduce other remaining pairs in the arrangement to the generated target number.
TEST 1: when nis even. Let n = 4, arr=[1,3,5,7]
There are 6 different arrangement of pairs for this array.
{1,3}, {5,7}
{1,5},{3,7}
{1,7},{3,5}
{3,5},{1,7}
{5,7},{1,3}
i. {1,3} reduces to {2,2} in 1 operation. Then target number = 2
{5,7}→ It is not possible to reduce elements of this pair to 2.
ii. {1,5} reduces to {3,3} in 2 operations. Then target number = 3 {3,7}→ It is not possible to reduce 7 to 3.
iii. {1,7} reduces to {4,4} in 3 operations. Then target number =4 {3,5} reduces to {4,4} in 1 operation.
Thus, 4 operations are required to reduce all elements to 4.
iv. {3,5} reduces to {4,4} in 1 operation. Then target number = 4
{1,7} reduces to {4,4} in 3 operations.
Thus, 4 operations are required to reduce all elements to 4.
v. {3,7} reduces to {5,5} in 2 operations. Then target number = 5
{1,5} → It is not possible to change 1 to 5.
vi. {5,7} reduces to {6,6} in 1 operation. Then target number = 6
{1,3} → It is not possible to change the elements of this pair to 6
We Found a Pattern
Voila! we found the pattern we’re looking for. Steps iii and iv give the required solution. Notice that steps iii and iv are the same process in the opposite direction. Whichever pattern you take will definitely give you a solution. By step iii, here are important points to note:
1) The target number is the number of operations required to make the two middle elements equal. Then the minimum operation is achieved when all other remaining pairs are reduced to this target number.
2) A pair is made up of 2 elements that are at the same distance from the center of the array. See the image below.
3) Given a pair of array elements say {a,b}, the number of operations requires to make them equal to the target number is half of the positive difference between the two elements of the pair i.e. (b-a)/2 where b > a.
4) From the image below, arr[i] forms a pair with arr[n-i-1]. Since arr[i]=(2*i)+1 and arr[n-i-1] > arr[i], the number of operation required to reduce the pair {arr[i], arr[n-i-1)} to the target number is calculated as follows
=(arr[n-i-1]-arr[i])/2
= (2(n-i-1) — (2i +1))/2
= n-2i-1
Since the total number of valid pairs are always equal to half of the array size i.e. n/2, The total minimum number of operations required to make all elements of an array of size n equal is the sum of alln-2i-1 where i= 0,1,...,(n/2)-1.
TEST 2: When n is odd. E.g. Let n= 5, then arr = [1,3,5,7,9].
Notice that in this case, all elements except one can form pairs. This means that since one element can never have a pair, such an element would serve as the target number. The question is which of the elements can serve as the target number? It turns out that we have to consider all possible pair arrangements taking each element as the target number. Notice that whenever an element is taken to be the target number, the remaining four elements can form only three distinct pair arrangements. For example, when the target number is 1, the following pairs are considered : {3,5},{7,9}, {3,7},{5,9}, {3,9},{7,5}.
Notice the difference with the previous arrangement when n is even. The target number was unknown, hence the order of pairs arrangement was important since the first pair was always used to generate the target number.
Thus, for each of the 5 possible target numbers, there are 3 possible pairs arrangements. This means that there are 5*3 = 15 arrangements to check. This might be time-consuming and prone to errors during an actual interview. Instead, I would like to apply the same steps we found in Test 1. Since valid pairs are symmetric around the center of the array, the element at the center of the array will always be the target number.
For the current array,Target number = 5, the pair {3,7} requires 2operations to change its elements to 5. Also, the pair {1,9} requires 4operations to change its elements to 5. If you are able to check all other possible arrangements, you will notice that taking the middle element as the target number would give the optimal solution. Thus, when n is odd, the pair formation looks like the image below.
Having got a valid pattern, we can code our first implementation of the solution.
Analysis of the Above Approach
The time complexity of the above approach is O(n). The space complexity is constant since the actual array is never created.
Can we do better than this?
EFFICIENT IMPROVEMENT
It’s amazing how the hard-looking problem was reduced to a few lines of understandable code. But we can do more. This time we focus more on the number of operations needed at each step and the patterns that the numbers follow.
1)When n is even. If you take a bigger even number as n and calculate the number of operations i.e. n-2i-1 from i=0,1,2,...,(n/2)-1, you’ll get the following series n-1, n-3, ..., 7, 5, 3, 1 . When the series is reversed, you’ll get 1, 3, 5, 7, ..., n-3, n-1. If you remember from Math class, this is simply a series of odd numbers starting from 1 or an Arithmetic series with first element = 1 and common difference = 2. The number of elements in the series is exactly n/2. The required result is the sum of this series. Using the formula for the Sum of Arithmetic Series with n elements Sum of A.S = n(2a + (n-1)d)/2, where a= first element, d = common difference, we can calculate the minimum number of operations by substituting n = n/2, a= 1, and d= 2 in the Sum of A.S formula. Hence, Result = (n/2)(2a + (n/2 — 1)d)/2. With further simplification, Result = (n*n)/4.
2) When n is odd. Using the same approach as above, the following series are generated; 2, 4, 6, ..., n-3, n-1. This is the series of even numbers starting from 2. It is also an Arithmetic Series with n/2 elements where first number, a = 2, commonn difference, d = 2. Using the formula for Sum of A.S as above, the total number of operation required to make all elements in the array equal is also (n*n)/4. Below is the code implementation in Java.
Analysis
This is unbelievably amazing!. Only a single line of code and both time and space complexity are constant.
Conclusion
If you got to this point, Kudos! I believe you learned one or two. Always remember to look for patterns whenever you encounter unfamiliar problems. You can also find out how to find an element from an array that is not sorted, or how to find the shortest subarray that should be sorted in order to keep the whole array sorted.
Wilson :-)
