Introduction
For this current problem, we are given an array of elements and a value x. We need to find the minimum number of elements to be added to the array to make the array’s median equal to x. A median is a value that can be calculated using the formula (n+1)/2, where n is the number of elements in the array. That means the Median is the middlemost value of a sorted array.
Also see, Morris Traversal for Inorder and Rabin Karp Algorithm
Solution
Approach
Let’s have some simple examples to understand this problem.
Example1:
Say, we are provided with an array of elements as a = [3,2,4], x = 2.
So, before adding any element and after sorting the array, the array’s median is three as it is the middlemost value of the array. We can also verify it by using the formula (n+1)/2 = (3+1)/2 = 2, the second element is 3. But we need two as the Median. So by adding 1 to the array, we will get the array as [1,2,3,4]. Now (4+1)/2 = 2. So the second element is two, which is equal to the x value. So here, the minimum number of elements we added is one.
Example2:
Say, we are provided with an array of elements as a = [10, 20, 30], x = 40.
So, before adding any element and after sorting the array, the array’s median is 20 as it is the middlemost value of the array. We can also verify it by using the formula (n+1)/2 = (3+1)/2 = 2, and the second element is 20. But we need 40 as the Median. So first, we check how many elements are less than the value x, equals x, and greater than the value x. So, here all the array elements are less than x, i.e., the number of elements that are less than x is 3. So if we have four more elements (if we add three more elements, then the number of elements will be even, i.e., 6, by using the formula, we will get 30 as the Median), then we can get the Median as of x. Thus by adding 40, 50, 50, and 50 to the array, we can get the array as [10,20,30,40,50,50,50]. Now on checking the formula, we will get the Median as 40.
Here we can observe that, on just checking the array, to find how many elements are greater than x, equal to x, and less than x, we can easily find the minimum number of elements to get added to make the Median equal to x. We can use this approach.
We can have two formulae in this approach:
If the number of elements greater than x is 'g,' the number of elements equal to x is 'e,' and the number of elements less than x is 'l.' Then,
if 'l' is greater than 'h', then, the answer will be (l - h) + 1 - e;
And if the value of 'h' is greater than 'l,' then the answer will be (h - l -1) + 1 - e;
In this problem, we just need to print the minimum number of elements to add to make the median equal to x but not to print the elements to be added. So we can follow the below algorithm:
Step1: Initialize the variables l, h, e
Step2: Initiate the loop to traverse through the array once.
Step3: Calculate the ‘l’ value by checking the number of elements less than x.
Step4: Calculate the ‘g’ value by checking the number of elements greater than x.
Step5: Calculate the ‘e’ value by checking the number of elements that equals x.
Step6: Calculate the answer by checking the above given two conditions.
Step7: Finally, return the answer as ans+1-e.
Code
Python:
def Solution(arr, x):
n = len(arr)
answer = 0
#Step1: initialise the variables
l, g, e = 0, 0, 0
#Step2: initialise the loop to traverse through the array
for i in arr:
if i ==x: #to calculate the value of 'e'
e+=1
elif i > x: #to calculate the value of 'g'
g+=1
elif i < x: #to calculate the value of 'l'
l+=1
if l > g: #Checking the conditions to calculate the answer
answer = l - g
elif l < g:
answer = g - l - 1
return answer+1-e #returning the answer.
arr = [10, 20, 30]
x = 40
print(Solution(arr, x))
Output:
4
The time complexity for this python solution code is O(n).
You can find this solution in different languages by referring to this GFG blog.